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 E implements Runnable{
	public static void main (String[] args) {new Thread(null, new E(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		int n = fs.nextInt(), maxBits = Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
		
		boolean[] used = new boolean[n+1];
		long res = 0;
		int[] perm = new int[n + 1]; Arrays.fill(perm, -1);
		for(int bits = maxBits; bits >= 0; bits--) {
			for(int i = n; i >= 0; i--) {
				if(perm[i] != -1) continue;
				int and = (1 << (bits + 1)) - 1;
				int optimal = (~i) & and;
				if(optimal > n || used[optimal]) continue;
				perm[i] = optimal; used[optimal] = true;
				res += i ^ optimal;
			}
		}
		if(perm[0] == -1) perm[0] = 0;
		
		StringBuilder sb = new StringBuilder();
		sb.append(res).append("\n");
		for(int i = 0; i <= n; i++) {
			if(i > 0) sb.append(" ");
			sb.append(perm[i]);
		}
		out.println(sb);
		
		out.close();
	}
	
	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}