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
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const long long Mod = 1e9 + 7;
const long double Pi = acos(-1);
int n;
long long Sum;
int Arr[1000009];
struct NODE {
  int Crnt;
  NODE *Bit[2];
  NODE() {
    Crnt = 0;
    Bit[0] = Bit[1] = NULL;
  }
} *Root = new NODE;
void Add(NODE *Node, int Pos, int Num) {
  if (Pos == -1) {
    Node->Crnt++;
    return;
  }
  int Nxt = ((Num & (1 << Pos)) > 0);
  if (Node->Bit[Nxt] == NULL) Node->Bit[Nxt] = new NODE;
  Add(Node->Bit[Nxt], Pos - 1, Num);
  int Ret = 0;
  for (int i = 0; i < 2; i++) {
    if (Node->Bit[i] == NULL) continue;
    Ret += Node->Bit[i]->Crnt;
  }
  Node->Crnt = Ret;
}
void Del(NODE *Node, int Pos, int Num) {
  if (Pos == -1) {
    Node->Crnt--;
    return;
  }
  int Nxt = ((Num & (1 << Pos)) > 0);
  Del(Node->Bit[Nxt], Pos - 1, Num);
  int Ret = 0;
  for (int i = 0; i < 2; i++) {
    if (Node->Bit[i] == NULL) continue;
    Ret += Node->Bit[i]->Crnt;
    if (Node->Bit[i]->Crnt == 0) {
      Node->Bit[i] = NULL;
    }
  }
  Node->Crnt = Ret;
}
int Query(NODE *Node, int Pos, int Num, int Ans) {
  if (Pos == -1) return Ans;
  int Nxt = ((Num & (1 << Pos)) > 0);
  if (Node->Bit[0] == NULL && Node->Bit[1] == NULL) return Ans;
  if (Node->Bit[1 - Nxt] == NULL)
    return Query(Node->Bit[Nxt], Pos - 1, Num, Ans + (Nxt) * (1 << Pos));
  return Query(Node->Bit[1 - Nxt], Pos - 1, Num, Ans + (1 - Nxt) * (1 << Pos));
}
int main() {
  memset(Arr, -1, sizeof(Arr));
  cin >> n;
  for (int i = 0; i <= n; i++) Add(Root, 21, i);
  for (int i = n; i >= 0; i--) {
    if (Arr[i] + 1) continue;
    int x = i, y = Query(Root, 21, x, 0);
    Del(Root, 21, x);
    if (x != y) Del(Root, 21, y);
    Arr[x] = y;
    Arr[y] = x;
    Sum += (x ^ y) * 2;
  }
  cout << Sum << endl;
  for (int i = 0; i <= n; i++) cout << Arr[i] << " ";
  cout << endl;
}
