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 OddEvenSort
{
  static void oddEvenMerge(int a[], int m) 
  {
    if (m > 2)
    {
      int[] ae = new int[m / 2];
      int[] ao = new int[m / 2];
      for (int i = 0; i < m / 2; i++) 
      {
        ae[i] = a[2 * i];
        ao[i] = a[2 * i + 1]; 
      }
      oddEvenMerge(ae, m / 2);
      oddEvenMerge(ao, m / 2);
      a[0] = ae[0];
      for (int i = 1; i < m / 2; i++)
        if (ae[i] <= ao[i - 1]) 
        {
          a[2 * i - 1] = ae[i];
          a[2 * i] = ao[i - 1]; 
        }
        else 
        {
          a[2 * i - 1] = ao[i - 1];
          a[2 * i] = ae[i]; 
        } 
      a[m - 1] = ao[m / 2 - 1]; 
    }
    else // m == 2
      if (a[0] > a[1])
      {
        int x = a[0]; a[0] = a[1]; a[1] = x;
      }
  }

  static void sort(int[] a, int n)
  {
    for (int m = 2; m <= n; m = m << 1) 
      for (int low = 0; low < n; low += m)
      {
        int[] b = new int[m];
        for (int i = 0; i < m; i++)
          b[i] = a[i + low];
        oddEvenMerge(b, m);
        for (int i = 0; i < m; i++)
          a[i + low] = b[i];
      }
  }
}

class OddEvenSortTest
{
  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();
    OddEvenSort.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();
  }
}