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.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


public class ProblemC {

	
	public static int[] match(int n) {
		int[] match = new int[n+1];
		if (n == 0) {
			return match;
		}
		if (n == 1) {
			match[0] = 1;
			return match;
		}
		
		int x = 1;
		while (x <= (n+1)) {
			x *= 2;
		}
		x /= 2;
		int amari = n - (x - 1);
		for (int i = 0 ; i < x - amari ; i++) {
			match[i] = x - i - 1;
		}
		for (int i = x - amari ; i < x ; i++) {
			match[i] = n - (i - (x - amari));
		}
		
		if (amari >= 1) {
			int[] submatch = match(amari-1);
			for (int i = x ; i <= n ; i++) {
				match[i] = submatch[i-x];
			}
		}
		return match;
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		
		long ans = 1L * n * (n + 1);
		int[] match = match(n);
		StringBuffer b = new StringBuffer();
		for (int i = 0 ; i <= n ; i++) {
			b.append(" ").append(match[i]);
		}
		out.println(ans);
		out.println(b.substring(1));
		out.flush();
	}
	
	

	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}

}
