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;
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / __gcd(a, b));
}
template <class T>
T power(T N, T P) {
  return (P == 0) ? 1 : N * power(N, P - 1);
}
template <class T>
string itoa(T a) {
  if (!a) return "0";
  string ret;
  for (T i = a; i > 0; i = i / 10) ret.push_back((i % 10) + 48);
  reverse(ret.begin(), ret.end());
  return ret;
}
double log(double N, double B) { return (log10l(N)) / (log10l(B)); }
vector<string> token(string a, string b) {
  const char *q = a.c_str();
  while (count(b.begin(), b.end(), *q)) q++;
  vector<string> oot;
  while (*q) {
    const char *e = q;
    while (*e && !count(b.begin(), b.end(), *e)) e++;
    oot.push_back(string(q, e));
    q = e;
    while (count(b.begin(), b.end(), *q)) q++;
  }
  return oot;
}
string toBin(int n) {
  string s;
  for (int i = 32 - 1; i >= 0; i--) s += ((bool)(n & (1 << (i))) + '0');
  return s;
}
bool eq(long double a, long double b) { return fabs(a - b) < 1e-9; }
int bit = 30;
struct trie {
  trie *next[3];
  int life;
  trie() {
    memset(next, 0, sizeof(next));
    ;
    life = 1;
  }
} * root;
int getlife(trie *c) {
  if (c == NULL) return 0;
  return c->life;
}
void del(int num, int p, trie *curr) {
  if (p == -1) {
    curr->life = 0;
    return;
  }
  int d = (bool)(bool)(num & (1 << (p)));
  del(num, p - 1, curr->next[d]);
  curr->life = getlife(curr->next[0]) | getlife(curr->next[1]);
}
void insert(int num, int p, trie *curr) {
  if (p == -1) {
    return;
  }
  int d = (bool)(bool)(num & (1 << (p)));
  if (curr->next[d] == NULL) curr->next[d] = new trie();
  insert(num, p - 1, curr->next[d]);
}
int query(int num, int &path) {
  path = 0;
  trie *curr = root;
  int ans = 0;
  for (int p = bit; p >= 0; p--) {
    int b = (bool)(bool)(num & (1 << (p)));
    int d = !b;
    if (curr->next[d] == NULL or curr->next[d]->life == 0) {
      d = !d;
    }
    if (b ^ d) ans = (ans | (1 << (p)));
    if (d) path = (path | (1 << (p)));
    curr = curr->next[d];
  }
  return ans;
}
int main() {
  root = new trie();
  int n, path;
  long long ans = 0;
  cin >> n;
  for (int i = 0; i < (int)n + 1; i++) insert(i, bit, root);
  vector<int> out;
  for (int i = 0; i < (int)n + 1; i++) {
    int add = query(i, path);
    out.push_back(path);
    ans += add;
    del(path, bit, root);
  }
  cout << ans << endl;
  for (int i = 0; i < (int)(int)out.size(); i++) cout << out[i] << " ";
  puts("");
}
