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;
void dumb(int n) {
  vector<int> perm, best;
  for (int i = 0; i <= n; i++) perm.push_back(i);
  int bestAnswer = -1;
  do {
    int answer = 0;
    for (int i = 0; i <= n; i++) answer += i ^ perm[i];
    if (answer > bestAnswer) {
      bestAnswer = answer;
      best = perm;
    }
  } while (next_permutation(perm.begin(), perm.end()));
  printf("n=%i:\n", n);
  printf("%i\n", bestAnswer);
  perm.clear();
  for (int i = 0; i <= n; i++) perm.push_back(i);
  do {
    int answer = 0;
    for (int i = 0; i <= n; i++) answer += i ^ perm[i];
    if (answer == bestAnswer) {
      for (unsigned i = 0; i < perm.size(); i++)
        printf("%i [%i] ", perm[i], perm[i] ^ i);
      printf("\n");
    }
  } while (next_permutation(perm.begin(), perm.end()));
  printf("\n");
}
vector<int> t;
void goBlessedx(int n) {
  if (n < 0) return;
  if (n == 0) {
    t[0] = 0;
    return;
  }
  if (n == 1) {
    t[0] = 1;
    t[1] = 0;
    return;
  }
  int k = 1;
  while (k <= n) k *= 2;
  int from = -1;
  for (int i = 0; i <= n; i++)
    if (k - i - 1 <= n) {
      if (from == -1) from = i;
      t[i] = n - (i - from);
    } else
      assert(from == -1);
  goBlessedx(from - 1);
}
void goBlessed(int n) {
  t.resize(n + 1);
  goBlessedx(n);
  for (int i = 0; i <= n; i++) printf("%i ", t[i]);
  printf("\n");
}
int main() {
  int n;
  scanf("%i", &n);
  printf("%I64d\n", ((long long)n) * (n + 1));
  goBlessed(n);
  return 0;
  for (int i = 1; i <= n; i++) dumb(i);
  goBlessed(7);
  goBlessed(6);
  goBlessed(3);
  goBlessed(2);
  goBlessed(5);
  return 0;
}
