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

public class Main
	{
	/*
	 * Simple bitmask code for boolean isset, int set and int clr
	 */
	public static boolean isset(int n,int i) //returns 1 if the ith bit (from left) of n is set
		{
		return ((n>>i)&1)==1;
		}

	public static int set(int n,int i) //makes the ith bit (from left) of n=1
		{
		return n|(1<<i);
		}

	public static int clr(int n,int i) //makes the ith bit (from left) of n=0
		{
		return n&(~(1<<i));
		}

	public static int max_set(int n)
		{
		for(int i=31;i>=0;i--)
			if(isset(n,i))
				return i;
		return 0;
		}
	public static void main(String args[]) throws IOException
		{
		InputReader in=new InputReader(System.in);
		int N=in.readInt();
		int A[]=new int[N+1];
		for(int i=0;i<=N;i++)
			A[i]=i;
		int B[]=new int[N+1];
		int index=N;
		while(index>0)
			{
			int newIndex=0;
			int maxSet=max_set(index);
			for(int i=0;i<=maxSet;i++)
				{
				if(isset(index,i))
					newIndex=clr(newIndex,i);
				else
					newIndex=set(newIndex,i);
				}
			//System.out.println("index = "+index+" newIndex= "+newIndex);
			int iter=0;
			for(int i=newIndex;i<=index;i++)
				{
				B[i]=A[index]-iter;
				iter++;
				}
			index=newIndex-1;			
			}
		long score=0;
		for(int i=0;i<=N;i++)
			score+=(i^B[i]);
		StringBuffer ans=new StringBuffer("");
		for(int i=0;i<=N;i++)
			{
			ans.append(B[i]);
			ans.append(" ");
			}
		PrintWriter out=new PrintWriter(System.out);
		out.println(score);
		out.println(ans);
		
		out.close();
		}
	}

class InputReader
	{
	private InputStream stream;
	private byte[] buf=new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream)
		{
		this.stream=stream;
		}

	public int read()
		{
		if(numChars==-1)
			throw new InputMismatchException();
		if(curChar>=numChars)
			{
			curChar=0;
			try
				{
				numChars=stream.read(buf);
				} catch (IOException e)
				{
				throw new InputMismatchException();
				}
			if(numChars<=0)
				return -1;
			}
		return buf[curChar++];
		}

	public int readInt()
		{
		int c=read();
		while (isSpaceChar(c))
			c=read();
		int sgn=1;
		if(c=='-')
			{
			sgn=-1;
			c=read();
			}
		int res=0;
		do
			{
			if(c<'0'||c>'9')
				throw new InputMismatchException();
			res*=10;
			res+=c-'0';
			c=read();
			} while (!isSpaceChar(c));
		return res*sgn;
		}

	public boolean isSpaceChar(int c)
		{
		if(filter!=null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
		}

	public static boolean isWhitespace(int c)
		{
		return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
		}

	public char readCharacter()
		{
		int c=read();
		while (isSpaceChar(c))
			c=read();
		return (char) c;
		}

	public interface SpaceCharFilter
		{
		public boolean isSpaceChar(int ch);
		}
	}
