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 .
Expression means applying the operation of bitwise excluding "OR" to numbers xand 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
题意：
给0~n，n+1个数让你找出一种排列，使得第i个位置上的数字与i做异或运算，然后所有运算结果加和，求使得加和最大排列。
思路：
首先，我们应该知道两个数做异或运算是相同为1，不同为0，即两个数都看成二进制，每一位都做运算，这一位上两个都是1或都是0，那么运算结果是0，否则为1。
如果想要最后的加和最大，那么尽量 就不要让两个数的二进制有重合的1，，因为如果有重合的1，那么异或完之后的结果一定会比两个数直接加和要小，如果没有冲突的1，那么两个数异或完后的结果应该等于两个数的加和。因此我们可以把二进制每一位都是1的数找出来，打个表。然后从后往前找，先找最后一个数n,从表中找到大于等于他的第一个数，然后两个数的差，就是最好的和n匹配的数，然后以这两个数为端点，同时向中间缩进，每一个数一定都是符合条件的最大的（可以自己写一下看看），接下来把最大的端点换成上次循环的起点的前一个数，重复循环，直到起点为0为止。
这道题目应该注意的是，最后的加和会很大所以应该开longlong,其次打表时，要注意范围，看看打的长度够不够。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<set>
#include<iostream>
#include<map>
#include<stack>
#include<cmath>
#include<algorithm>
#define ll long long
#define mod 1000000007
#define eps 1e-8
using namespace std;
int num[1010101];
int main()
{int n,k;ll sum=0;//加和很大记得开longlong scanf("%d",&n);int one[100]={0};one[1]=1;for(int i=2;i<=24;i++){one[i]=(one[i-1]<<1)+1;//打表后，要看看是不是比给的范围大，不要打小了 }int ne=n;while(1){int tt=*lower_bound(one,one+23,ne);int ff=tt-ne;for(int st=tt-ne,ed=ne;st<ed;ed--,st++){sum+=(st^ed)*2;num[st]=ed;num[ed]=st;}ne=tt-ne-1;if(ff==0||ne<0)break;} printf("%lld\n",sum);printf("%d",num[0]);for(int i=1;i<=n;i++){printf(" %d",num[i]);}putchar('\n');}