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.util.*;
import java.io.*;
import java.math.*;
public class Main {
    public static void main(String[] args){
//      px(Integer.toBinaryString(Integer.MAX_VALUE));
        Scanner scan = new Scanner(System.in);
        int n1 = scan.nextInt();
        long sum = n1;
        sum = sum * (sum + 1l);
        int[] l1 = new int[n1 + 1];
        Arrays.fill(l1, -1);
        int bits = 31;
        for (int i = l1.length - 1; i >= 0; i--){
            if (l1[i]!= -1) continue;
            for (;;){
                int mask = (1 << bits) - 1;
                int xor = i ^ mask;
                if (xor > n1 || l1[xor] != -1){
                    bits--;
                }
                else {
                    l1[i] = xor;
                    l1[xor] = i;
                    break;
                }
            }
        }
//      px(l1);
        out.println(sum);
        for (int e: l1){
            out.print(e+" ");
        }
        out.flush();
    }
    static PrintWriter out = new PrintWriter(System.out);
    static void px(Object ...objects){
        System.out.println(Arrays.deepToString(objects));
    }
}
