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.*;

public class Main
{
    static int ans = 0 ;
    static String print ;
    static void bt(int index , int n , int sol , boolean [] vis , String s)
    {
        if(index > n)
        {
            if(ans <= sol)
            {
                System.out.println(sol+" "+s);
                ans = sol ;
                print = s ;
            }
            return ;
        }
        for(int i = 0 ; i <= n ; i ++ )
            if(!vis[i])
            {
                boolean [] newVis = vis.clone() ;
                newVis[i] = true;
                bt(index + 1 , n , sol + (index ^ i), newVis , s + i+" ");
            }
    }

    public static void main(String[] args) throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out) ;
        int n = sc.nextInt() ;
//        bt(0 , n , 0 , new boolean[n + 1] , "");
//        out.println(ans);
//        System.out.println(print);
        boolean [] vis = new boolean[n + 1] ;
        int [] ans = new int [n + 1] ;
        Arrays.fill(ans , -1);
        for(int l = 20 ; l >= 0 ; l --)
        {
            int mask = (1 << l) - 1 ;
            for(int i = n ; i >= 0 ; i--)
            {
                int next = mask ^ i ;
                if(0 <= next && next <= n && !vis[next] && ans[i] == -1)
                {
                    vis[next] = true ;
                    ans[i] = next ;
                }
            }
        }
        long tot = 0 ;
        for(int i = 0 ; i <= n ; i++) tot += i ^ ans[i] ;
        out.println(tot);
        for(int x : ans) out.print(x+" ");
        out.flush();
    }

    static class Scanner
    {
        BufferedReader br ;
        StringTokenizer st ;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(in)) ;
        }
        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken() ;
        }
        int nextInt() throws Exception { return Integer.parseInt(next()) ; }

        long nextLong() throws Exception {return Long.parseLong(next());}

        double nextDouble() throws Exception {return Double.parseDouble(next());}

    }
}