Codeforces 177 E

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;
int vis;

int main()
{
int tmp;
long long sum=0;
cin>>n;
while(p<=n)
{
p<<=1;
}
for(int i=n;i;i--)
if(0==vis[i])
{
//cout<<i<<" find "<<tmp<<endl;
if(tmp<=n)
{
vis[i]=1;
vis[tmp]=1;
a[i]=tmp;
a[tmp]=i;
}
else
{
tmp_p=1;
{
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)cout<<a;
else cout<<0;
for(int i=1;i<=n;i++)
cout<<" "<<a[i];
return 0;
}