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

/**
 * @author icemore
 */
public class Main {
    
    int getBase(int n)
    {
        int base=1;
        while(n!=0)
        {
            base<<=1;
            n>>=1;
        }
        
        return base-1;
    }
    
    void solve() throws IOException
    {
        int n=nextInt()+1;
        int[] a= new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i]=-1;
        }
        
        for(int i=n-1; i>=0; --i)
        {
            if(a[i]!=-1) continue;
            int base=getBase(i);
            //System.err.println(i+" - "+(base^i));
            
            a[i]=base^i;
            a[base^i]=i;
        }
        
        long res=0;
        for (int i = 0; i < n; i++) {
            res+=(long)a[i]^i;
        }
        
        out.println(res);
        for (int i = 0; i < n; i++) {
            out.print(a[i]+" ");
        }
    }
    
    //<editor-fold defaultstate="collapsed" desc="Template">
    
    double nextDouble() throws IOException
    {
        return Double.parseDouble(nextToken());
    }
    
    long nextLong() throws IOException
    {
        return Long.parseLong(nextToken());
    }
    
    int nextInt() throws IOException
    {
        return Integer.parseInt(nextToken());
    }
    
    String nextToken() throws IOException
    {
        while(st==null || !st.hasMoreTokens())
        {
            st = new StringTokenizer(br.readLine());
        }
        
        return st.nextToken();
    }
    
    void run() throws IOException
    {
        boolean onlineJudge = System.getProperty("ONLINE_JUDGE")!=null;
        Reader reader = onlineJudge ? new InputStreamReader(System.in) : new FileReader("input.txt");
        Writer writer = onlineJudge ? new OutputStreamWriter(System.out) : new FileWriter("output.txt");
        
        br = new BufferedReader(reader);
        out = new PrintWriter(writer);
        solve();
        out.close();   
    }
    
    public static void main(String[] args) throws IOException {
        new Main().run();
    }
    
    StringTokenizer st;
    BufferedReader br;
    PrintWriter out;
    //</editor-fold>
}
