import java.io.*;

class Intsort {

  private static void swap(int[] arr, int s, int t)
  {
    int tmp = arr[s];  arr[s] = arr[t];  arr[t] = tmp;
  }

  // Selection sort

  public static void selsort(int[] arr, int n)
       // sort arr[0..n-1]
  {                                             /* pp1 */
    for (int i = 0; i < n; i++)
      {                                         /* pp2 */
        int least = i;                                      
        for (int j = i+1; j < n; j++)
          { 
            if (arr[j] < arr[least])
              least = j;
          }
        swap(arr, i, least);                    /* pp3 */
      }                                         /* pp4 */
  }

  // Quicksort

  private static void qsort(int[] arr, int a, int b) {
    if (a < b)
      { 
        int i = a, j = b;
        int x = arr[(i+j) / 2];                 /* pp1 */
        do {                                    /* pp2 */
         while (arr[i] < x) i++;                /* pp3 */
         while (arr[j] > x) j--;                /* pp4 */
         if (i <= j)
           {
             swap(arr, i, j);
             i++; j--;
           }                                    /* pp5 */
        } while (i <= j);                       /* pp6 */
        qsort(arr, a, j);                       /* pp7 */
        qsort(arr, i, b);                       /* pp8 */
      }                                         /* pp9 */
  }

  public static void quicksort(int[] arr, int n)
  {
    qsort(arr, 0, n-1);
  }

  // Heapsort

  private static void heapify(int[] arr, int i, int k)
       // heapify node arr[i] in the tree arr[0..k]
  {
    int j = 2 * i + 1;                          /* pp1 */
    if (j <= k)
      {
        if (j+1 <= k && arr[j] < arr[j+1])
          j++;                                  /* pp2 */
        if (arr[i] < arr[j])
          {
            swap(arr, i, j);                    /* pp3 */
            heapify(arr, j, k);                 /* pp4 */
          }           
      }                                         /* pp5 */
  }

  public static void heapsort(int[] arr, int n)
  {
    for (int m=n/2; m >= 0; m--) 
      heapify(arr, m, n-1);
                                                /* pp1 */
    for (int m=n-1; m >= 1; m--)
      {                                         /* pp2 */
        swap(arr, 0, m);                        /* pp3 */
        heapify(arr, 0, m-1);                   /* pp4 */
      }                                         /* pp5 */
  }

  public static int[] fillarray(int n)
  {
    int [] arr = new int[n];
    for (int i = 0; i < n; i++)
      arr[i] = (int) (Math.random() * 30000);
    return arr;
  }

  public static void printout(int[] arr, int n)
  {
    for (int i=0; i < n; i++)
      System.out.print(arr[i] + " ");
    System.out.println("");
  }

  public static boolean sorted(int[] arr, int n)
  {
    if (n == 0) 
      return true;
    int last = arr[0];
    int i = 1;
    while (i < n && last <= arr[i])
      {
        last = arr[i];
        i++;
      }
    return i == n;
  }

  public static int readfile(int[] arr, String filename) 
       throws FileNotFoundException, IOException
  {
    int n = 0;
    Reader inp = new FileReader(filename);
    StreamTokenizer tstream = new StreamTokenizer(inp);
    
    tstream.parseNumbers();
    tstream.nextToken();
    while (n < arr.length && tstream.ttype == StreamTokenizer.TT_NUMBER)
      {
	arr[n] = (int) tstream.nval; tstream.nextToken();
	n++;
      }
    return n;
  }

  public static int readstring(int[] arr, String s) 
       throws IOException
  {
    int n = 0;
    Reader inp = new StringReader(s);
    StreamTokenizer tstream = new StreamTokenizer(inp);
    
    tstream.parseNumbers();
    tstream.nextToken();
    while (n < arr.length && tstream.ttype == StreamTokenizer.TT_NUMBER)
      {
	arr[n] = (int) tstream.nval; tstream.nextToken();
	n++;
      }
    return n;
  }
}