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.io.ObjectInputStream.GetField;
import java.math.*;
import java.text.*;
import java.util.*;

//Codeforces
public class MainCodeforces1 {
	private static MyScanner in;
	private static PrintStream out;

	public static void main(String[] args) throws IOException {
		// helpers for input/output
		boolean LOCAL_TEST = false;// change to false before submitting
		out = System.out;
		if (LOCAL_TEST) {
			in = new MyScanner("E:\\zin2.txt");
		}
		else {
			boolean usingFileForIO = false;
			if (usingFileForIO) {
				// using input.txt and output.txt as I/O
				in = new MyScanner("input.txt");
				out = new PrintStream("output.txt");
			}
			else {
				in = new MyScanner();
				out = System.out;
			}
		}

		solve();
	}

	private static void solve() throws IOException
	{
		int n = in.nextInt();
		long sum = 0;
		List<Integer> nums = new ArrayList<Integer>();
		HashSet<Integer> used = new HashSet<Integer>();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i <= n; i++) {
			int x = 1048575;
			int p = ~i & x;
			while (p > n || used.contains(p)) {
				x = x >> 1;
				p = ~i & x;
			}
			int num = p ^ i;
			sum += num;
			nums.add(p);
			used.add(p);
			if (i > 0)
				sb.append(" ");
			sb.append(p);
		}
		out.println(sum);
		out.println(sb);
	}

	// =====================================
	static class MyScanner {
		Scanner inp = null;

		public MyScanner() throws IOException
		{
			inp = new Scanner(System.in);
		}

		public MyScanner(String inputFile) throws IOException {
			inp = new Scanner(new FileInputStream(inputFile));
		}

		public int nextInt() throws IOException {
			return inp.nextInt();
		}

		public long nextLong() throws IOException {
			return inp.nextLong();
		}

		public double nextDouble() throws IOException {
			return inp.nextDouble();
		}

		public String nextString() throws IOException {
			return inp.next();
		}

	}

}