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 long long int mod = 1e9 + 7;
const long long int inf = 1e17;
bool cmp(pair<long long int, long long int>& a,
         pair<long long int, long long int>& b) {
  if (a.first != b.first)
    return a.first > b.first;
  else
    return a.second < b.second;
}
vector<long long int> parent, size, visited, a, b;
vector<long long int> ans, xv;
vector<vector<long long int>> adj;
long long int modval(long long int n) { return n % mod; }
long long int modadd(long long int a, long long int b) {
  return modval(modval(a) + modval(mod + modval(b)));
}
long long int modmul(long long int a, long long int b) {
  return modval(modval(a) * modval(b));
}
long long int fast_expo(long long int base, long long int power,
                        long long int ans) {
  if (power > 0) {
    if (power & 1) ans = modmul(ans, base);
    power >>= 1, base = modmul(base, base);
    return fast_expo(base, power, ans);
  } else
    return ans;
}
long long int find_set(long long int v) {
  if (v == parent[v]) return v;
  return find_set(parent[v]);
}
void make_set(long long int v) {
  parent[v] = v;
  size[v] = 1;
}
void union_sets(long long int a, long long int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (size[a] < size[b]) swap(a, b);
    parent[b] = a;
    size[a] += size[b];
  }
}
long long int findmsb(long long int n) {
  for (long long int i = 29; i >= 0; i--) {
    if (n >= (1 << i)) return i;
  }
}
void ceasars_legions() {
  long long int n;
  scanf("%lld", &n);
  long long int a[n + 1], sum = 0;
  a[n] = -1;
  for (long long int i = n, x; i >= 0; i--) {
    if (a[i] == -1) {
      if (i != 0) {
        x = 1 << findmsb(i);
        x += x - 1;
        if (x - i > 0) a[x - i - 1] = -1;
      } else
        x = 0;
    }
    a[i] = x - i;
    sum += a[i] + i;
  }
  cout << sum << '\n';
  for (long long int i = 0; i <= n; i++) printf("%lld ", a[i]);
}
int32_t main() {
  long long int t = 1;
  while (t--) ceasars_legions();
  return 0;
}
