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.*;

public class C{

    static int [] matching(int n) {

        int [] res = new int [n+1];
        if ((n& (n+1)) == 0)
            for (int i=0; i<=n;  i++)
                res[i] = n-i;
        else {
            int last = n;
            int pos = n;
            while (last > 1) {
                if ((last & (last+1)) == 0) {
                    for (int i=0; i<= last; i++)
                        res[i] = last-i;
                    break;
                }
                else {
                    while ( (last & (last+1)) != 0) last --;
                    int num = pos - last;
                    for (int i=1; i<=num; i++) {
                        res[last+i] = last-i+1;
                        res[last-i+1] = last+i;
                    }
                    pos = last-num;
                    last = pos;
                }
            }
            if (last == 1) {
                res[0] = 1;
            }
        }
           return res;

    }


    public static void main(String [] argv) {
        Kattio io= new Kattio(System.in, System.out);
        int n = io.getInt();
        int [] res = matching(n);
        io.println((long)n*((long)(n+1)));
        for (int i: res)
            io.print(i + " ");
        io.println();
        io.close();
    }

}


// ############ KATTIO ##########
 class Kattio extends PrintWriter {
    public Kattio(InputStream i) {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(i));
    }
    public Kattio(InputStream i, OutputStream o) {
        super(new BufferedOutputStream(o));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }



    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}
