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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class PenguinAndXOROperation {
    public static void main(String[] args){
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int[] arr = new int[n+1];
        boolean[] used = new boolean[n+1];
        long sum =0;
        int obt = (1<<(32 - Integer.numberOfLeadingZeros(n)))-1;
        for(int i=arr.length-1;i>=0;i--){
            int guess = obt ^ i;
            while(guess > n || used[guess]){
                obt >>=1;
                guess = obt & guess;
            }
            if(!used[guess]){
                arr[i] = guess;
                used[guess] = true;
                sum += (guess ^ i);
            }
        }
        System.out.println(sum);
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n+1;i++){
            sb.append(arr[i]);
            if(i != n){
                sb.append(" ");
            }
        }
        System.out.println(sb);
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
