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.util.StringTokenizer;

public class Main {
    void solve() {
        int n = ni();
        int cur = n;
        long m = 0;
        int[] out = new int[n + 1];
        while (cur > 0) {
            int mask = getMask(cur);
            int next = (cur ^ mask) - 1;
            while ((cur ^ mask) < cur && cur >= 0) {
                int p = cur ^ mask;
                out[cur] = p;
                out[p] = cur;
                m += mask << 1;
                cur--;
            }
            cur = next;
        }
        write(m + "\n");
        for (int i = 0; i <= n; i++) {
            write(out[i] + " ");
        }
    }

    int getMask(int n) {
        int mask = 1;
        while (mask <= n) {
            mask = mask << 1;
        }
        mask -= 1;
        return mask;
    }


    public static void main(String[] args){
        Main m = new Main();
        m.solve();
        try {
            m.writer.close();
        } catch (IOException e) {};
    }
    BufferedReader reader;
    BufferedWriter writer;
    StringTokenizer tokenizer;
    public Main() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new BufferedWriter(new OutputStreamWriter(System.out));
    }
    int ni() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {}
        }
        return Integer.parseInt(tokenizer.nextToken());
    }
    String nl() {
        try {
            return reader.readLine();
        } catch(IOException e) {};
        return "";
    }
    void write(String s) {
        try {
            writer.write(s);
        } catch(IOException e) {};
    }
}