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.LinkedList;
import java.util.Scanner;
import java.util.Stack;


public class PoloPenguinAndXOR {


	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		logOf2 = Math.log(2);
//		while (s.hasNext())
//		{
//			perm = new LinkedList<Integer>();
			
			
//			toPrint = "";
//			added = 0;
			n = s.nextInt();
			permutationArray = new long[n+1];
			index = n;
			int m = n;
			long ret = 0;
			do
			{
				ret = solve(m);
				m-=ret;
			} while (ret != 0);
			
			System.out.println(answer);
//			System.out.println(solve(n));
//			String answerString = "";
			for (int i = 0;i < n;i++)
			{
				System.out.print(permutationArray[i]+" ");
//				answerString += perm.pop() + " ";
//				System.out.print(perm.pop()+" ");
			}
			System.out.println(permutationArray[n]);
//			System.out.println(answerString + perm.pop());
//			System.out.println(perm.pop());
//			System.out.println(toPrint.trim());
//			for (int i = 0; i <= n ; i++)
//			{
////				System.out.println("ON "+i);;
//				for (int j = 0; j <= n ; j++)
//				{
//					System.out.print((i ^ j)+",");
//				}
//				System.out.println();
//			}
//		}
		s.close();
	}
	
//	static LinkedList<Integer> perm;
	static int n;
	static long answer = 0;
	
	static long[] permutationArray;
	static int index;
//	static String toPrint;
//	static int added;
	
	private static long solve(long m)
	{
		if (m==0)
		{
//			System.out.println("size "+perm.size());
//			System.out.println("n " + m);
//			if (perm.size() == n)
//			{
//				
//				perm.push(0);
//			}
			if (index == 0)
				permutationArray[0] = 0;
			
//			if (added == n)
//				toPrint = "0 "+toPrint;
			return 0;
		}
//		int p = getCeilPowTwo(m);
		double twoToThePMinusOne = Math.pow(2, (Math.floor(Math.log(m)/logOf2)));
		
		long bigValue = (long) ( twoToThePMinusOne * 2 - 1);
		long numBigs = (long) (2*(m-(twoToThePMinusOne)+1));
		
		
//		System.out.println("CompBV "+bigValue+" "+bigValue2);
//		System.out.println("CompNB "+numBigs+" "+numBigs2);
		
		for (long i = m - numBigs+1; i <= m  ; i++)
		{
//			toPrint = i+" "+toPrint;
//			added++;
//			perm.push(i);
			permutationArray[index] = i;
			index--;
		}
		answer += bigValue * numBigs;
		return numBigs;
	}
	
	static double logOf2;
	
	
}