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

public class cf288C {
	static InputReader in = new InputReader();
	static String str;
	static String[] arr;

	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(in.readLine());
		int[] ans = new int[n + 1];
		solve(n + 1, ans);
		StringBuilder sb = new StringBuilder("");
		for(int i = 0; i < n + 1; i++) {
			sb.append(ans[i]);
			sb.append(i == n ? "\n" : " ");
		}
		System.out.println((long) n * (n + 1));
		System.out.print(sb.toString());
	}

	public static void solve(int n, int[] ans) {//n = size
		n--;
		if(n <= 0) return;
		int maxpow = 1 << (int) Math.floor(Math.log(n) / Math.log(2));
		for(int i = maxpow; i <= n; i++) {
			ans[i] = maxpow * 2 - i - 1;
			ans[maxpow * 2 - i - 1] = i;
		}
		solve(2 * maxpow - n - 1, ans);
	}
	
	static class InputReader {
		BufferedReader br;

		public InputReader() {
			try {
				br = new BufferedReader(new FileReader("cf288C.in"));
			} catch(Exception e) {
				br = new BufferedReader(new InputStreamReader(System.in));
			}
		}

		public String readLine() throws Exception {
			return br.readLine();
		}
	}
}