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 int maxn = 1000000 + 5;
long long pre[32];
int ans[maxn];
long long len(int x) {
  long long ret = 0;
  while (x) {
    ret++;
    x = x / 2;
    ;
  }
  return ret;
}
int main() {
  int n;
  long long total;
  pre[0] = 0;
  pre[1] = 1;
  for (int i = 2; i < 32; i++) pre[i] = (pre[i - 1] << 1) + 1;
  while (cin >> n) {
    memset(ans, -1, sizeof(ans));
    total = 0;
    for (int i = n; i >= 0; i--) {
      if (ans[i] == -1) {
        int j = pre[len(i)] - i;
        ans[i] = j;
        ans[j] = i;
        total += 2 * pre[len(i)];
      }
    }
    cout << total << endl;
    for (int i = 0; i <= n; i++) printf("%d ", ans[i]);
    cout << endl;
  }
  return 0;
}
