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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class C {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[] a = new int[n+1];
        int[] mask = new int[21];
        int pow = 2;
        for (int i=0; i<21; i++) {
            mask[i] = pow-1;
            pow*=2;
        }
        Arrays.fill(a, 0);
        long res = 0;
        int p = n;
        while (p > 0) {
            int i=0;
            pow = 1;
            while (pow <= p) {i++; pow*=2;}
            i--;
            int px = p ^ mask[i];
            for (int j=0; p-j >= px+j; j++) {
                a[p-j] = px+j;
                a[px+j] = p-j;
            }
            p = px-1;
            if (p < 0) break;
        }
        for (int i=0; i<=n; i++) {
            res += i^a[i];
        }
        System.out.println(res);
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<n; i++) sb.append(a[i]).append(" ");
        sb.append(a[n]);
        System.out.println(sb.toString());
    }
    
}
