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

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();
  }
} 

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

class Prefix
{
  int n;
  int[] a;

  Prefix(int n)
  {
    this.n = n;
    a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = i;
  }
 
  void sequentialPrefix()
  {
    for (int i = 1; i < n; i++)
        a[i] += a[i - 1];
  }

  void recursivePrefix(int low, int n)
  {
    if (n > 1)
    {
      recursivePrefix(low, n / 2); 
      recursivePrefix(low + n / 2, n - n / 2); 
      for (int i = n / 2; i < n; i++) 
        a[low + i] += a[low + n / 2 - 1]; 
    }
  }

  void parallelPrefix()
  {
    for (int step = 1; step <= n / 2; step *= 2)
      for (int i = step - 1; i < n; i += 2 * step)
        a[i + step] += a[i];
    for (int step = n / 4; step >= 1; step /= 2)
      for (int i = 3 * step - 1; i < n; i += 2 * step) 
        a[i] += a[i - step];
  }

  void print()
  {
    for(int i = 0; i < n; i++)
      System.out.println("a[" + i + "] = " + a[i]);
    System.out.println();
  }
}

class PrefixTest
{
  public static void main(String[] args)
  {
    int n;
    long t;
    Prefix p;
    System.out.print("\nGive log n   >>>   ");
    n = 1 << IO.readInt();

    System.out.println("\nSequential algorithm:");
    p = new Prefix(n);
    t = - Clock.now();
    p.sequentialPrefix();
    t += Clock.now();
    if (n < 100)
      p.print();
    else
      System.out.println("Computation took " + t + " milli seconds");

    System.out.println("Recursive algorithm:");
    p = new Prefix(n);
    t = - Clock.now();
    p.recursivePrefix(0, n);
    t += Clock.now();
    if (n < 100)
      p.print();
    else
      System.out.println("Computation took " + t + " milli seconds");

    System.out.println("Parallel algorithm:");
    p = new Prefix(n);
    t = - Clock.now();
    p.parallelPrefix();
    t += Clock.now();
    if (n < 100)
      p.print();
    else
      System.out.println("Computation took " + t + " milli seconds\n");
  }
}