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;
int a[1000088];
int use[1000088];
int main() {
  int n;
  while (cin >> n) {
    long long ans = 0;
    memset(use, -1, sizeof(use));
    for (int i = n; i >= 0; i--) {
      if (use[i] == -1) {
        int num = 0;
        int tmax = 0;
        int t1 = i;
        while (1) {
          num++;
          if (t1 & 1) {
            tmax = num;
          }
          if (num > 30) break;
          t1 = t1 >> 1;
        }
        t1 = ~i;
        int t2 = ~(-1 << tmax);
        t1 = t1 & t2;
        if (use[t1] == -1) {
          use[t1] = i;
          use[i] = t1;
          ans += (t1 ^ i) * 2;
        }
      }
    }
    cout << ans << endl;
    for (int i = 0; i <= n; i++) {
      if (i)
        cout << " " << use[i];
      else
        cout << use[i];
    }
    puts("");
  }
  return 0;
}
