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.*;
import java.math.*;

public class Csmart implements Runnable {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	final static int maxNodes = 2000020, maxLog = 22;
	static int nodeCount = 1;

	void solve() throws IOException {
		int n = nextInt();

		int[] zero = new int[maxNodes], one = new int[maxNodes];

		Arrays.fill(zero, -1);
		Arrays.fill(one, -1);

		for (int i = 0; i <= n; i++)
			addPos(i, zero, one);

		int[] p = new int[n + 1];
		for (int i = n; i >= 0; i--)
			p[i] = getPos(i, zero, one);

		long res = 0;
		for (int i = 0; i <= n; i++)
			res += i ^ p[i];
		
		out.println(res);
		for (int i = 0; i <= n; i++) {
			out.print(p[i]);
			out.print((i == n) ? "\n" : " ");
		}
	}

	private void addPos(int n, int[] zero, int[] one) {
		int ptr = 0;
		
		//out.println("Add pos: " + n);

		for (int bit = maxLog; bit >= 0; bit--) {
			int curValue = getValue(n, bit);
			int[] nextArr = (curValue == 0) ? zero : one;

			if (nextArr[ptr] == -1)
				nextArr[ptr] = nodeCount++;

			ptr = nextArr[ptr];
		}
	}

	private int getValue(int n, int bit) {
		boolean empty = (n & (1 << bit)) == 0;
		return empty ? 0 : 1;
	}

	private int getPos(int n, int[] zero, int[] one) {
		//out.println("GetPos:" + n);
		return getPosRec(n, maxLog, 0, zero, one, 0);
	}

	private int getPosRec(int n, int bit, int ptr, int[] zero, int[] one,
			int value) {
		if (bit == -1)
			return value;

		int curValue = getValue(n, bit), result = 0;
		boolean found = false;

		// try best
		{
			int[] nextArr = (curValue == 0) ? one : zero;
			int addValue = (curValue == 0) ? (1 << bit) : 0;
			int nextNode = nextArr[ptr];
			if (nextNode != -1) {
				int newValue = value + addValue;
				result = getPosRec(n, bit - 1, nextNode, zero, one, newValue);
				found = true;
				
				// remove links
				if(isEmpty(bit - 1, nextNode, zero, one))
					nextArr[ptr] = -1;
			}
		}

		// try bad
		if (!found) {
			int[] nextArr = (curValue == 0) ? zero : one;
			int addValue = (curValue == 0) ? 0 : (1 << bit);
			int nextNode = nextArr[ptr];
			if (nextNode != -1) {
				int newValue = value + addValue;
				result = getPosRec(n, bit - 1, nextNode, zero, one, newValue);
				found = true;
				
				// remove links
				if(isEmpty(bit - 1, nextNode, zero, one))
					nextArr[ptr] = -1;
			}
		}

		if (!found)
			throw new AssertionError();

		return result;
	}

	private boolean isEmpty(int bit, int ptr, int[] zero, int[] one) {
		return (zero[ptr] == -1 && one[ptr] == -1);
	}

	public static void main(String[] args) {
		new Csmart().run();
	}

	public void run() {
		try {
			final String className = this.getClass().getName().toLowerCase();

			try {
				in = new BufferedReader(new FileReader(className + ".in"));
				out = new PrintWriter(new FileWriter(className + ".out"));
				// in = new BufferedReader(new FileReader("input.txt"));
				// out = new PrintWriter(new FileWriter("output.txt"));
			} catch (FileNotFoundException e) {
				in = new BufferedReader(new InputStreamReader(System.in));
				out = new PrintWriter(System.out);
			}

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(42);
		}
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

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

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

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