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.*;
import java.math.*;
import java.util.*;

public class Main implements Runnable {
    public static void main(String[] args) {
        new Thread(new Main()).start();
    }
    public void run() {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt(), m = n;
        int[] perm = new int[n + 1];
        while (m >= 0) {
            int p = 0;
            while (m >> p > 0) p++;
            if (m == 0) {
                perm[m--] = 0;
            }
            else {
                int v = m - (1 << p >> 1) + 1;
                for (int i = 0; i < v; ++i) {
                    perm[m - i] = m - v - v + i + 1;
                    perm[m - v - v + i + 1] = m - i;
                }
                m -= v + v;
            }
        }
        long ret = 0;
        for (int i = 0; i <= n; ++i)
            ret += perm[i] ^ i;
        out.println(ret);
        for (int i = 0; i <= n; ++i)
            if (i == n) {
                out.println(perm[i]);
            }
            else {
                out.print(perm[i] + " ");
            }
        out.close();
    }
}
