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;
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << " | ";
  err(++it, args...);
}
void inpll() {}
template <typename T, typename... Args>
void inpll(T &a, Args &...args) {
  scanf("%lld", &a);
  inpll(args...);
}
void inpi() {}
template <typename T, typename... Args>
void inpi(T &a, Args &...args) {
  scanf("%d", &a);
  inpi(args...);
}
void inplf() {}
template <typename T, typename... Args>
void inplf(T &a, Args &...args) {
  scanf("%lf", &a);
  inplf(args...);
}
int main() {
  long long i, n, k, p, j, ans[1000009], u, l;
  cin >> n;
  for (__typeof(n + 1) i = (0) - ((0) > (n + 1));
       i != (n + 1) - ((0) > (n + 1)); i += 1 - 2 * ((0) > (n + 1)))
    ans[i] = i;
  for (__typeof(0) i = (n + 1) - ((n + 1) > (0)); i != (0) - ((n + 1) > (0));
       i += 1 - 2 * ((n + 1) > (0))) {
    j = i;
    p = 0;
    l = 1;
    while (j) {
      k = j & (-j);
      j = j - k;
      p += l * (2 * k - 1);
      j /= (2 * k);
      l *= 2 * k;
    }
    p = p ^ i;
    if ((i ^ p) > (i ^ ans[i]) and ans[i] == i and ans[p] == p) {
      ans[i] = p;
      ans[p] = i;
    }
    u += i ^ ans[i];
  }
  cout << u << endl;
  for (i = 0; i <= n; i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
