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;
bool check(long long n, long long pos) {
  return (n & ((long long)1 << pos)) >> pos;
}
const long long M = 100;
long long A[1001000];
long long leftbit(long long n) {
  for (long long i = 28; i >= 0; i--)
    if (check(n, i)) return i;
}
int main() {
  long long i, j, k, n;
  memset((A), (-1), sizeof(A));
  scanf("%I64d", &n);
  long long sum = 0;
  for (i = n; i > 0; i--) {
    if (A[i] == -1) {
      k = leftbit(i);
      A[i] = ((1 << (k + 1)) - 1) ^ i;
      A[A[i]] = i;
      sum += ((1 << (k + 1)) - 1) * 2;
    }
  }
  if (A[0] == -1) A[0] = 0;
  printf("%I64d\n", sum);
  for (i = 0; i <= n; i++) printf("%I64d ", A[i]);
  printf("\n");
  ;
  return 0;
}
