import java.io.*;
import java.util.Date;
import java.util.Random;

class IO
{
  public static int readInt() 
  // Reads an int from standard input.
  {
    String input = "";
    try 
    {
      BufferedReader bufRead = new BufferedReader
        (new InputStreamReader (System.in));
      input = bufRead.readLine();
    } 
    catch (java.io.IOException e) 
    {
      System.out.print("Error while reading input line!\n");
    }
    return Integer.valueOf(input).intValue();
  }

  public static String intToString(int i, int size)
  // Converts an int into a string of length
  // size with leading blanks added.
  {
    String output = Integer.toString(i);
    while (output.length() < size)
      output = " " + output;
    return output;
  }
} 

class Clock 
{
  static long now()
  // returns the current time in miliseconds
  {
    return (new Date()).getTime();
  }
}

class BitonicSort
{
  static void bitonicMergeUp(int[] a, int low, int m)
  {
    for (int s = m >> 1; s > 0; s = s >> 1)
      for (int i = low; i < low + m; i += 2 * s)
        for (int j = i; j < i + s; j++)
          if (a[j] > a[j + s])
          {
            int x = a[j]; a[j] = a[j + s]; a[j + s] = x;
          }
  }

  static void bitonicMergeDn(int[] a, int low, int m)
  {
    for (int s = m >> 1; s > 0; s = s >> 1)
      for (int i = low; i < low + m; i += 2 * s)
        for (int j = i; j < i + s; j++)
          if (a[j] < a[j + s])
          {
            int x = a[j]; a[j] = a[j + s]; a[j + s] = x;
          }
  }

  static void sort(int[] a, int n)
  {
    for (int m = 2; m < n; m = m << 1) 
      for (int low = 0; low < n; low += 2 * m)
      {
        bitonicMergeUp(a, low,     m);
        bitonicMergeDn(a, low + m, m);
      }
    bitonicMergeUp(a, 0, n);
  }
}

class BitonicSortTest
{
  public static void main(String[] args)
  {
    Random random = new Random(Clock.now());
    System.out.print("\nGive log n   >>>   ");
    int n = 1 << IO.readInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = random.nextInt(n);
    System.out.println();
    long t = - Clock.now();
    BitonicSort.sort(a, n);
    t += Clock.now();
    System.out.println("Sorting completed after " + t + " milliseconds");
    System.out.println();
    if (n < 100)
      for (int i = 0; i < n; i++)
        System.out.println("a[" + IO.intToString(i, 2) + "] = " +
          IO.intToString(a[i], 11));
    else
    {
      int i;
      for (i = 1; i < n && a[i - 1] <= a[i]; i++);
      if (i == n)
        System.out.println("Sorting tested: correct");
      else
        System.out.println("Sorting tested: NOT correct!");
    }
    System.out.println();
  }
}