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.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Vector;

public class CmdProgram {
    protected StringTokenizer tokenizer;
    protected PrintWriter outputWriter;
    protected BufferedReader inputReader;
    
    public CmdProgram(){
        this.inputReader = new BufferedReader(new InputStreamReader(System.in));
        this.outputWriter = new PrintWriter(System.out);
    }
    
    public String nextInput(){
        return this.tokenizer.nextToken();
    }
    
    public int nextInt(){
        return Integer.parseInt(nextInput());
    }
    
    public long nextLong(){
        return Long.parseLong(nextInput());
    }
    
    public void nextLine() throws IOException{
        this.tokenizer = new StringTokenizer(this.inputReader.readLine());
    }
    
    public static void main(String[] args) throws Exception{
        PenguinPoloXOR polo = new PenguinPoloXOR();
        polo.nextLine();
        long n = polo.nextInt();
        long p = n;
        while(n > -1){
            int k = -1;
            do{
                k++;
            }while(Math.pow(2, k)<=n);
            polo.answer.insertElementAt((long)Math.pow(2, k) - 1 - n, 0);
            if((long)Math.pow(2, k) - 1 - n == 0){
                break;
            }else{
                n = (long)Math.pow(2, k) - 2 - n;
            }
        }
        
        long num = p*(p+1);
        
        polo.outputWriter.write(String.valueOf(num));
        polo.outputWriter.write(" ");
        polo.outputWriter.flush();
        for(int i = 0; i<polo.answer.size()-1; i++){
            long start = (Long) polo.answer.get(i);
            long end = (Long) polo.answer.get(i+1);
            for(; start < end; end--){
                polo.outputWriter.write(String.valueOf(end-1));
                polo.outputWriter.write(" ");
            }
            polo.outputWriter.flush();
        }
        for(; p >= (Long)polo.answer.lastElement(); p--){
            polo.outputWriter.write(String.valueOf(p));
            polo.outputWriter.write(" ");
        }
        polo.outputWriter.close();
    }
}

class PenguinPoloXOR extends CmdProgram {

    public Vector answer = new Vector();
    
}
