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

public class Main {
	
	static int[] unit(int[] x, int[] y) {
		int[] z = new int[x.length + y.length];
		int ind = 0;
		for (int xx : x) z[ind++] = xx;
		for (int xx : y) z[ind++] = xx;
		return z;
	}

	static int[] opt(int n) {
		if (n == -1) return new int[] {};
//		if (n == 0) return new int[] {0};
		int k = 1;
		while ((k << 1) <= n + 1) k <<= 1;
		int[] x = new int[k];
		for (int i = 0; i < 2*k - n - 1; i++) x[i] = k - 1 - i;
		for (int i = 2*k - n - 1; i < k; i++) x[i] = k - 1 - i + k;
		return unit(x, opt(n - k));
	}

	public static void main(String[] args) throws Exception {
		long time = System.nanoTime();

		int n = next();

		int[] x = opt(n);
		long sum = 0;
		for (int i = 0; i <= n; i++) sum += (x[i] ^ i);
		out.println(sum);
		for (int xx : x) out.print(xx + " ");
		out.println();
		
//		System.out.println((System.nanoTime() - time)* 1e-9);
		out.close();
	}
	static PrintWriter out = new PrintWriter(System.out);
	
	static BufferedReader bufferedreader = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer in = new StringTokenizer("");

	static String nextToken() throws Exception {
		if (!in.hasMoreTokens()) in = new StringTokenizer(bufferedreader.readLine());
		return in.nextToken();
	}

	static int next()  throws Exception {return Integer.parseInt(nextToken());};
	static int[] next(int n) throws Exception {
		int[] x = new int[n];
		for (int i = 0; i < n; i++) x[i] = next();
		return x;
	}
	static int[][] next(int n, int m) throws Exception {
		int[][] x = new int[n][];
		for (int i = 0; i < n; i++) x[i] = next(m);
		return x;
	}

	static long nextl() throws Exception {return Long.parseLong(nextToken());};
	static long[] nextl(int n) throws Exception {
		long[] x = new long[n];
		for (int i = 0; i < n; i++) x[i] = nextl();
		return x;
	}
	static long[][] nextl(int n, int m) throws Exception {
		long[][] x = new long[n][];
		for (int i = 0; i < n; i++) x[i] = nextl(m);
		return x;
	}

	static double nextd() throws Exception {return Double.parseDouble(nextToken());};
	static double[] nextd(int n) throws Exception {
		double[] x = new double[n];
		for (int i = 0; i < n; i++) x[i] = nextd();
		return x;
	}
	static double[][] nextd(int n, int m) throws Exception {
		double[][] x = new double[n][];
		for (int i = 0; i < n; i++) x[i] = nextd(m);
		return x;
	}

	static String nextline() throws Exception {
		in = new StringTokenizer("");
		return bufferedreader.readLine();
	}

}