import java.io.*;

/** Class for finding the minimum number in an array, the maximum, or both at once */
class MinMax {
    
    //fields:
    private static int[] nums;
    private static int n;
    private static int c=0;
    
    //methods:
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader 
            (new InputStreamReader(System.in)); 
        System.out.println("Enter the number of numbers:");
        String str = stdin.readLine(); 
        n = Integer.parseInt(str);
        nums = new int[n];
        
        if (n==0){
            System.out.println("Well, never mind then.");}
        else {
            System.out.println("Enter the numbers, one on each line:");
            
            for (int i = 0; i < n; i++){
                str = stdin.readLine();
                nums[i] = Integer.parseInt(str);}
            
            getBoth(nums, n);}
    }//method main()
    
    /** Finds and displays the largest and smallest integer from the array */    
    public static void getBoth(int[] A, int size) {
        //init variables
        int i, max, min, maxListLength, minListLength, temp;
        int[] minList, maxList;
        double best;
        
        //[1] -- Definition of some variables
        temp = size/2;
        minList = new int[temp + 1]; //Add an extra element to MinList in case
        maxList = new int[temp];     //size is odd (see [3]).
        minListLength = size/2; //These variables will be updated later if
        maxListLength = size/2; //necessary (in the case of odd size).
        
        //size of 1 will cause errors later, so deal with it separately
        if (size==1)
        {
            System.out.println("Max: " + A[0] + "\nMin: " + A[0]);
            System.out.println("No comparisons necessary");
            return;
        }
        
        //[2] -- Separate
        //Main loop to separate into two groups ("winners" and "losers")
        //Goes 2 at a time, and only to (size - 1) because it looks at the
        //element after i, and there is no element after i=size. Thus,
        //it skips the last element if size is odd. See [3].
        for (i = 0; i < (size - 1); i += 2){
            if (greaterThan(A[i], A[i+1])){
                maxList[i/2] = A[i];
                minList[i/2] = A[i+1];
            }
            else {
                minList[i/2] = A[i];
                maxList[i/2] = A[i+1];
            }
        }
        
        //[3] -- Special Case: size is odd
        //The following chunk of code deals with arrays containing an odd
        //number of numbers.
        if (size % 2 != 0){
            //If there is an odd number of numbers, grab the last number and
            //deal with it, because the loop didn't.
            
            //Check the last element against an element of maxList and copy
            //it to minList or maxList, as is appropriate. 
            //This allows the previous for loop to ignore the last number.
            if (greaterThan(A[size - 1], maxList[0])){
                //The last element of A can replace the first element of maxList
                //if the last element of A "wins," because it means that first
                //element of maxList is no longer a candidate for the maximum.
                //This will result in 3/2*n-2.5 comparisons by the end.
                maxList[0] = A[size - 1];
            }
            else {
                //If the last element of A loses, we add it to minList and leave
                //maxList alone. This will result in 3/2*n-1.5 comparisons.
                minList[minListLength] = A[size - 1];
                minListLength++;
            }
        }
        
        //[4] -- Find Max and Min
        //Now, find the maximum of the "winners" and the minimum of the "losers":
        max = getMax(maxList, maxListLength);
        min = getMin(minList, minListLength);
        
        //[5] -- Display
        System.out.println("Max: " + max);
        System.out.println("Min: " + min);
        System.out.println("Comparisons: " + c);
        best = java.lang.Math.ceil(3*size/2.0-2);
        System.out.println("ceil(3/2*n-2): " + best);
    }//method getBoth()
    
    /** Essentially a wrapper for the ">" operation, but also keeps track of how many
     * comparisons are formed via the class variable c
     */    
    public static boolean greaterThan(int a, int b)
    {
        c++;
        return (a > b);
    }//method greaterThan()
    
    /** Returns the largest integer from the array */    
    public static int getMax(int[] A, int size) {
        int i, max;
        max = A[0];

        for (i=1; i < size; i++){
            if (greaterThan(A[i], max)) max=A[i];}
        
        return max;
    }//method getMax()
    
    /** Returns the smallest integer from the array */    
    public static int getMin(int[] A, int size) {
        int i, min;
        min = A[0];
        
        for (i=1; i < size; i++){
            if (greaterThan(min, A[i])) min = A[i];
        }
        
        return min;
    }//method getMin()
    
}//class MinMax