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 neg(int n) {
  int res = 0;
  int k = 0;
  int h = 1;
  while (n != 0) {
    int k = n % 2;
    if (k == 0)
      k = 1;
    else
      k = 0;
    res = (k * h) + res;
    n = n / 2;
    h = h * 2;
  }
  return res;
}
int main() {
  int n;
  cin >> n;
  vector<pair<int, int> > v;
  int i = n;
  long long sum = 0;
  while (i != -1) {
    int k = neg(i);
    v.push_back(make_pair(i, k));
    i = k - 1;
  }
  vector<int> vv;
  for (int j = v.size() - 1; j >= 0; j--) {
    int a = v[j].first;
    int b = v[j].second;
    for (int h = a; h >= b; h--) vv.push_back(h);
  }
  for (int i = 0; i < vv.size(); i++) {
    sum += (i ^ vv[i]);
  }
  cout << sum << endl;
  for (int i = 0; i < vv.size(); i++) cout << vv[i] << " ";
  cout << endl;
  return 0;
}
