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 MAXN = 1000010;
const long long MOD = 1e9 + 7;
int N;
int digit[25], len;
bool vis[MAXN];
int ans[MAXN];
int fac[25];
int main() {
  cin >> N;
  fac[0] = 1;
  for (int i = 1; i < 25; i++) fac[i] = fac[i - 1] * 2;
  int maxlen = 0;
  int tmp = N;
  while (tmp) {
    tmp /= 2;
    maxlen++;
  }
  for (int i = N; i >= 0; i--) {
    len = 0;
    int tmp = i;
    memset(digit, 0, sizeof(digit));
    while (tmp) {
      digit[len++] = tmp % 2;
      tmp /= 2;
    }
    tmp = 0;
    for (int j = 0; j < maxlen; j++) digit[j] ^= 1;
    for (int j = 0; j < maxlen; j++) {
      if (digit[j] == 1) {
        if (tmp + fac[j] > N) break;
        tmp += fac[j];
      }
    }
    for (int j = tmp; j; j = (j - 1) & tmp) {
      if (vis[j]) continue;
      vis[j] = true;
      ans[i] = j;
      break;
    }
  }
  long long ret = 0;
  for (int i = 0; i <= N; i++) ret += i ^ ans[i];
  printf("%I64d\n", ret);
  for (int i = 0; i <= N; i++) printf("%d%c", ans[i], i == N ? '\n' : ' ');
  return 0;
}
