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 size = 10000004;
const long long inf = 1e18;
const long long modulo = 1000000007;
vector<int> parent, rang;
int compo;
void make_set(int v) {
  parent[v] = v;
  rang[v] = 0;
}
int find_set(int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
  int pa = find_set(a), pb = find_set(b);
  if (pa != pb) {
    if (rang[pa] < rang[pb]) swap(pa, pb);
    parent[pb] = pa;
    if (rang[pa] == rang[pb]) rang[pa]++;
  }
}
int best = 0;
vector<vector<int> > ans;
void gen(vector<int>& a, int l, int r) {
  if (l == r) {
    int sum = 0;
    for (int i = 0; i < a.size(); i++) sum += (i ^ a[i]);
    if (sum == best) {
      ans.push_back(a);
    } else if (sum > best) {
      ans.clear();
      ans.push_back(a);
      best = sum;
    }
  } else {
    for (int i = l; i <= r; i++) {
      swap(a[i], a[l]);
      gen(a, l + 1, r);
      swap(a[i], a[l]);
    }
  }
}
int main() {
  long long n;
  cin >> n;
  vector<int> p2(25, 0), a(n + 1, 0);
  for (int i = 1; i <= 22; i++) {
    p2[i] = (p2[i - 1] + 1) * 2 - 1;
  }
  for (int i = n; i > 0;) {
    int l;
    for (int j = 22; j >= 0; j--) {
      if (p2[j] - i < i) {
        l = p2[j] - i;
        break;
      }
    }
    int new_i = l - 1, r = i;
    for (int j = l; j <= i; j++, r--) a[j] = r;
    i = new_i;
  }
  cout << n * (n + 1) << endl;
  for (int i = 0; i <= n; i++) cout << a[i] << ' ';
  cout << endl;
}
