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 MOD = 1000000007;
int A[10];
int used[10];
int good[10];
class MissingParentheses {
 public:
  long long pow(int n, int k) {
    long long res = 1;
    long long sqr = n;
    while (k) {
      if (k % 2 == 0) {
        sqr = (sqr * sqr) % MOD;
        k /= 2;
      } else {
        res = (res * sqr) % MOD;
        k--;
      }
    }
    return res;
  }
  int test(int i) {
    if (!used[i]) {
      used[i] = 1;
      good[i] = test(A[i]);
    }
    return good[i];
  }
  void countCorrections() {
    long long n;
    cin >> n;
    long long sum = 0;
    vector<int> A(n + 1, 0);
    vector<int> P(n + 1, -1);
    for (int i = 0; i <= n; i++) {
      A[i] = i;
      sum += A[i];
    }
    cout << 2 * sum << "\n";
    int p = 1 << 25;
    for (int i = n; i >= 0; i--) {
      if (P[i] == -1) {
        if (i == 0) {
          P[i] = 0;
          break;
        }
        while ((i & p) == 0) {
          p /= 2;
        }
        int j = (i ^ p ^ (p - 1));
        P[i] = j;
        P[j] = i;
      }
    }
    for (int i = 0; i <= n; i++) {
      cout << P[i] << " ";
    }
  }
};
int main() {
  MissingParentheses alg;
  alg.countCorrections();
}
