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.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	int reverse (int num, int bits) {
		int result = 0;
		for (int i = bits - 1; i >= 0; i--) {
			result <<= 1;
			if (((1 << i) & num) == 0) result++; 
		}
		return result;
	}
	
	int bitLength (int num) {
		int result = 0;
		while (num > 0) {
			result++;
			num >>= 1; 
		}
		return result;
	}
	
	long result = 0;
	int n;
	/*
	int perm [];
	boolean used [];
	
	void rec (int k) {
		if (k == n + 1) {
			long cur = 0;
			for (int i = 0; i <= n; i++)
				cur += i ^ perm[i];
			if (cur > result) {
				out.println("FUCK");
				for (int i = 0; i <= n; i++) {
					out.print(perm[i]+" ");
				}
				out.println();
			}
		} else {
			for (int i = 0; i <= n; i++) {
				if (!used[i]) {
					used[i] = true;
					perm[k] = i;
					rec (k + 1);
					used[i] = false;
				}
			}
		}
	}
	*/
	public void solve () throws Throwable {
		n = sc.nextInt();
		int match [] = new int [n + 1];
		int ans [] = new int [n + 1];
		Arrays.fill(match, -1);
		for (int i = n; i >= 0; i--) {
			if (match[i] != -1) {
				ans[i] = match[i];
			} else {
				int rev = reverse(i, bitLength(i));
				match[rev] = i;
				ans[i] = rev;
			}
		}
		for (int i = 0; i <= n; i++) {
			result += (i ^ ans[i]);
		}
		out.println(result);
		for (int i = 0; i <= n; i++) {
			out.print(ans[i]+" ");
		}
		
		/*
		perm = new int [n + 1];
		used = new boolean [n + 1];
		rec (0);
		*/
	}

	BufferedReader in;
	PrintWriter out;
	FastScanner sc;

	static Throwable uncaught;
	
	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable t) {
			Solution.uncaught = t;
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) throws Throwable {
		Thread t = new Thread(null, new Solution(), "", (1 << 26));
		t.start();
		t.join();
		if (uncaught != null) {
			throw uncaught;
		}
	}

}

class FastScanner {

	BufferedReader reader;
	StringTokenizer strTok;

	public FastScanner(BufferedReader reader) {
		this.reader = reader;
	}

	public String nextToken() throws IOException {
		while (strTok == null || !strTok.hasMoreTokens()) {
			strTok = new StringTokenizer(reader.readLine().trim());
		}
		return strTok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

}