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 n;
int trie[2][5000000 + 5];
int cant[5000000 + 5];
int s[5000000 + 5];
bool flags[5000000 + 5];
int idx = 1;
void insert(int x) {
  int node = 0;
  for (int i = 0; i < 22; i++) {
    int bit = 0;
    if (x & (1LL << i)) bit = 1;
    if (trie[bit][node] == -1) trie[bit][node] = idx++;
    node = trie[bit][node];
    cant[node]++;
  }
}
pair<int, int> query(long long x) {
  long long sum = 0LL;
  long long num = 0LL;
  int node = 0;
  for (int i = 0; i < 22; i++) {
    int bit = 0;
    if (x & (1 << i)) bit = 1;
    int opp = 0;
    if (bit == 0) opp = 1;
    if (trie[opp][node] != -1 && cant[trie[opp][node]] > 0) {
      sum += (1LL << i);
      if (opp == 1) num += (1LL << i);
      node = trie[opp][node];
    } else {
      if (opp == 1)
        opp = 0;
      else
        opp = 1;
      if (opp == 1) num += (1LL << i);
      node = trie[opp][node];
    }
  }
  return {num, sum};
}
void remove(long long x) {
  int node = 0;
  for (int i = 0; i < 22; i++) {
    int bit = 0;
    if (x & (1 << i)) bit = 1;
    int next = trie[bit][node];
    cant[next]--;
    node = next;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  memset(trie, -1, sizeof(trie));
  for (int i = 0; i <= n; i++) insert(i);
  long long solve = 0LL;
  int pos = 0;
  if (n % 2 == 0) pos = 1;
  for (int i = n; i >= pos; i--) {
    if (!flags[i]) {
      pair<int, int> A = query(i);
      flags[i] = flags[A.first] = true;
      if (i != A.first)
        solve += 2LL * A.second;
      else
        solve += A.second;
      s[i] = A.first;
      s[A.first] = i;
      remove(i);
      remove(A.first);
    }
  }
  cout << solve << '\n';
  for (int i = 0; i <= n; i++) cout << s[i] << " ";
  cout << '\n';
  return 0;
}
