Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.

For permutation p = p0, p1, ..., pn, Polo has defined its beauty — number <image>.

Expression <image> means applying the operation of bitwise excluding "OR" to numbers x and y. This operation exists in all modern programming languages, for example, in language C++ and Java it is represented as "^" and in Pascal — as "xor".

Help him find among all permutations of integers from 0 to n the permutation with the maximum beauty.

Input

The single line contains a positive integer n (1 ≤ n ≤ 106).

Output

In the first line print integer m the maximum possible beauty. In the second line print any permutation of integers from 0 to n with the beauty equal to m.

If there are several suitable permutations, you are allowed to print any of them.

Examples

Input

4


Output

20
0 2 1 4 3
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class cf288c {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int n = in.nextInt();
    int[] v = new int[n+1];
    while(n > 0) {
      int other = Integer.highestOneBit(n)<<1;
      other--;
      other ^= n;
      int a = other, b = n;
      n = a-1;
      while(a < b) {
        v[a] = b;
        v[b] = a;
        a++;
        b--;
      }
    }
    long ans = 0;
    for(int i=0; i<v.length; i++) {
      ans += i^v[i];
    }
    out.println(ans);
    for(int x : v) out.print(x+ " ");
    out.close();
  }
}
