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


public class Main {
  
   // public static long[][]   dp = new long[5005][5005];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t,ca,i,j;
		
		String[] my;
		String line = br.readLine();
        my = line.split(" ");
        int n = Integer.parseInt(line);
        int a[] = new int[n+1];
        for(i=n;i>0;i--)
        {
            if(a[i]==0)
            {
                int x = get(i);
                a[i] = x;
                a[x] = i;
            }
        }
        StringBuffer bf = new StringBuffer();
        System.out.println((long)n*(n+1));
        for(i=0;i<=n;i++)
           bf.append(a[i] + " ");
           System.out.println(bf.toString());
        }
    public static int get(int m)
    {
        int n = m;
        int c = 1;
        while(n>1){
            n/=2;
            c++;
        }
        c  = 1<<c;
        c = c-1;
        return c-m;
    }
}
class ut implements Comparator<Team>{
    public int compare(Team first, Team other)
    {
          if(first.pr > other.pr)return -1;
        if(first.pr < other.pr)return 1;
        if(first.ti < other.ti)return -1;
        if(first.ti > other.ti)return 1;
        if(first.in < other.in)return -1;
        if(first.in > other.in)return 1;
        return 0;
    }
}
class Team implements Comparable{
    int pr,ti,in;
    public Team(int a, int b, int c)
    {
        pr = a;
        ti = b;
        in = c;
    }
    public String toString()
    {
        return pr + " " + ti + " " + in+ "\n";
    }
    public int compareTo(Object obj)
    {
        Team other = (Team)obj;
        if(pr > other.pr)return -1;
        if(pr < other.pr)return 1;
        if(ti < other.ti)return -1;
        if(ti > other.ti)return 1;
        if(in < other.in)return -1;
        if(in > other.in)return 1;
        return 0;
    }
}

