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.math.*;
import static java.lang.Math.*;
import java.security.SecureRandom;
import static java.util.Arrays.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import sun.misc.Regexp;
import java.awt.geom.*;
import java.awt.image.BufferedImage;
import javax.imageio.ImageIO;
import sun.net.www.content.text.plain;

public class Main {

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
    StreamTokenizer in;
    PrintWriter out;
//deb////////////////////////////////////////////////

    public static void deb(String n, Object n1) {
        System.out.println(n + " is : " + n1);
    }

    public static void deb(int[] A) {

        for (Object oo : A) {
            System.out.print(oo + " ");
        }
        System.out.println("");
    }

    public static void deb(long[] A) {

        for (Object oo : A) {
            System.out.print(oo + " ");
        }
        System.out.println("");
    }

    public static void deb(boolean[] A) {

        for (Object oo : A) {
            System.out.print(oo + " ");
        }
        System.out.println("");
    }

    public static void deb(double[] A) {

        for (Object oo : A) {
            System.out.print(oo + " ");
        }
        System.out.println("");
    }

    public static void deb(String[] A) {

        for (Object oo : A) {
            System.out.print(oo + " ");
        }
        System.out.println("");
    }

    public static void deb(int[][] A) {
        for (int i = 0; i < A.length; i++) {
            for (Object oo : A[i]) {
                System.out.print(oo + " ");
            }
            System.out.println("");
        }

    }

    public static void deb(double[][] A) {
        for (int i = 0; i < A.length; i++) {
            for (Object oo : A[i]) {
                System.out.print(oo + " ");
            }
            System.out.println("");
        }

    }

    public static void deb(long[][] A) {
        for (int i = 0; i < A.length; i++) {
            for (Object oo : A[i]) {
                System.out.print(oo + " ");
            }
            System.out.println("");
        }

    }

    public static void deb(String[][] A) {
        for (int i = 0; i < A.length; i++) {
            for (Object oo : A[i]) {
                System.out.print(oo + " ");
            }
            System.out.println("");
        }

    }
    /////////////////////////////////////////////////////////////

    int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    long nextLong() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    void run() throws IOException {
//          in = new StreamTokenizer(new BufferedReader(new FileReader("input.txt")));
        // out = new PrintWriter(new FileWriter("output.txt"));
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        solve();
        out.flush();
    }
//boolean inR(int x,int y){
//return (x<=0)&&(x<4)&&(y<=0)&&(y<4);
//}
static long aa=0;
void ff(int pos, int K ){
    if(pos==K){
        int chk=0;
        for (int i = 0; i < K; i++) {
           int st=a[i],ct=0;
            while(st!=0){
            st=a[st];ct++;
            if(ct>K+4){
            chk=1;break;
            }
            }
            if(chk==1)break;
        }
    if(chk!=1)aa++;
    }
    else
    for (int i = 0; i < K ; i++) {
        a[pos]=i;
        ff(pos+1,K);
    }

}

static int[] a=new int[8];
    @SuppressWarnings("unchecked")
    void solve() throws IOException {
        //   BufferedReader re= new BufferedReader(new FileReader("C:\\Users\\ASELA\\Desktop\\PROBLEMSET\\input\\F\\10.in"));
       //   BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
        //   Scanner sc = new Scanner(System.in);
  int N=nextInt();
  int[] A=new int[N+1];
  boolean[] vis= new boolean[N+1];
  long tot=0;
        for (int i = N; i > 0; i--) {
            if(!vis[i]){
            double dd=log(i)/log(2);
            int len=(int)dd+1;
            int kk=(int)pow(2,len)-1;
            tot+=2*kk;
            A[i]=i^kk;
            vis[A[i]]=true;
            vis[i]=true;
            A[A[i]]=i;
            
            }
        }
        out.println(tot);
        for (int i = 0; i < N+1; i++) {
            out.print(A[i]+" ");
        }
        out.println("");
    }
    
}
