Polo the Penguin and XOR operation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive. For permutation p = p0, p1, …, p__n, Polo has defined its beauty — number . Expression  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.

Sample test(s)

input

4

output

20 0 2 1 4 3


#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int a[1000005];
int vis[1000005];

int main()
{
    int n,mask=0,tmp_p,p=1;
    int tmp;
    long long sum=0;
    cin>>n;
    while(p<=n)
    {
        mask|=p;
        p<<=1;
    }
    //cout<<mask<<endl;
    for(int i=n;i;i--)
      if(0==vis[i])
      {
          tmp=((~i)&mask);
          //cout<<i<<" find "<<tmp<<endl;
          if(tmp<=n)
          {
              vis[i]=1;
              vis[tmp]=1;
              sum+=mask<<1;
              a[i]=tmp;
              a[tmp]=i;
          }
          else
          {
              tmp_p=1;
              //tmp=((~i)&(mask>>1));
              while((1<<tmp_p)<=mask)
              {
                  tmp=((~i)&(mask>>tmp_p));
                  if(0==vis[tmp])break;
                  tmp_p++;
              }
              vis[tmp]=1;
              vis[i]=1;
              sum+=(tmp^i)<<1;
              a[i]=tmp;
              a[tmp]=i;
          }
      }
    cout<<sum<<endl;
    if(vis[0])cout<<a[0];
    else cout<<0;
    for(int i=1;i<=n;i++)
      cout<<" "<<a[i];
    return 0;
}