class Minmax{

  static void P(String s){
    System.out.print(s);
  }

  // question a : on fait n-1 comparaisons
  static int minimum(int[] t, int n){
    int min = t[0];
    
    for(int i = 1; i < n; i++)
      if(t[i] < min)
	min = t[i];
    return min;
  }

  static int maximum(int[] t, int n){
    int max = t[0];

    for(int i = 1; i < n; i++)
      if(t[i] > max)
	max = t[i];
    return max;
  }

  // question b
  static int[] comparerDeuxEntiers(int a, int b){
    int[] t = new int[2];

    if(a < b){
      t[0] = a; t[1] = b;
    }
    else{
      t[0] = b; t[1] = a;
    }
    return t;
  }

  // question c : on fait 1+1+2 comparaisons
  static int[] minMaxQuatreEntiers(int a, int b, int c, int d){
    int[] tab = comparerDeuxEntiers(a, b);
    int[] tcd = comparerDeuxEntiers(c, d);
    int[] t = new int[2];
    
    if(tab[0] < tcd[0])
      t[0] = tab[0];
    else
      t[0] = tcd[0];
    if(tab[1] > tcd[1])
      t[1] = tab[1];
    else
      t[1] = tcd[1];
    return t;
  }

  // question d: min-max pour t[g..d[
  static int[] minMaxAux(int[] t, int g, int d){
    int gd = d-g;
    
    if(gd == 1){
      // min-max pour t[g..g+1[ = t[g], t[g]
      int[] u = new int[2];

      u[0] = u[1] = t[g];
      return u;
    }
    else if(gd == 2)
      return comparerDeuxEntiers(t[g], t[g+1]);
    else{ // gd > 3
      int m = (g+d)/2;
      int[] tg = minMaxAux(t, g, m); // min-max sur t[g..m[
      int[] td = minMaxAux(t, m, d); // min-max sur t[m..d[
      int[] u = new int[2];

      if(tg[0] < td[0])
	u[0] = tg[0];
      else
	u[0] = td[0];
      if(tg[1] > td[1])
	u[1] = tg[1];
      else
	u[1] = td[1];
      return u;
    }
  }

  static int[] minMax(int[] t){
    return minMaxAux(t, 0, t.length);
  }

  // question e) analyse de T(k) = nombre de comparaisons pour n=2^k
  // on T(1) = 1 d'après b), T(2) = 2*T(1)+2 d'après c)
  // D'après d), T(k) = 2*T(k-1)+2
  // T(k) = 2^2*T(k-2)+2^2+2 = 2^u*T(k-u)+2^u+2^(u-1)+...+2
  //      = 2^(k-1)*T(1)+2^(k-1)+...+2
  //      = 2^(k-1)+2^k-2 = n/2+n-2 = 3*n/2-2

  // programme de test
  public static void main(String[] args){
    int[] t = {1, 4, 6, 8, 2, 3, 6, 0};
    int[] u;

    P("min="+minimum(t, t.length)+"\n");
    P("max="+maximum(t, t.length)+"\n");
    u = minMax(t);
    P("minmax="+u[0]+" "+u[1]+"\n");
  }
}