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 Main {

	BufferedReader in;
	StringTokenizer str = null;
	PrintWriter out;
	
	private String next() throws Exception{
		if (str == null || !str.hasMoreElements())
			str = new StringTokenizer(in.readLine());
		return str.nextToken();
	}
	
	private int nextInt() throws Exception{
		return Integer.parseInt(next());
	}
	
	private long nextLong() throws Exception{
		return Long.parseLong(next());
	}
	
	private double nextDouble() throws Exception{
		return Double.parseDouble(next());
	}
	
	public void run() throws Exception{
		in =  new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		int n = nextInt()+1;
		int ret[] = new int[n];
		Arrays.fill(ret, -1);

		long s = 0;
		for(int i=n-1;i>=0;i--){
			if (ret[i] == -1) {
				int x = i, t = 0, k = 0;
				while(x > 0) {
					if ((x & 1) == 0)
						t|=1<<k;
					x>>=1;
					k++;
				}
				ret[i] = t;
				ret[t] = i;
				s+=2*(t^i);
			}
		}
		out.println(s);
		for(int i : ret){
			out.print(i + " ");
		}
		out.println();
		out.close();
	}

	private int inv(int x, int len) {
		int ret = 0;
		for(int i=0;i<len;i++){
			if ((x & (1 << i)) == 0) ret|=1<<i;
		}
		return ret;
	}
		
	public static void main(String[] args) throws Exception{
		new Main().run();
	}
}
