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;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T gcd(T a, T b) {
  return __gcd(a, b);
}
template <class T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
long long modpow(long long a, long long n, long long temp) {
  long long res = 1, y = a;
  while (n > 0) {
    if (n & 1) res = (res * y) % temp;
    y = (y * y) % temp;
    n /= 2;
  }
  return res % temp;
}
long long ison(long long mask, long long pos) { return (mask & (1 << pos)); }
long long cbit(long long n) {
  long long k = 0;
  while (n) n &= (n - 1), k++;
  return k;
}
long long nbit(long long n) {
  long long k = 0;
  while (n) n /= 2, k++;
  return k;
}
long long mod = 1e9 + 7;
int sgn(long long x) { return x < 0 ? -1 : !!x; }
const double eps = 1e-7;
const double pi = acos(-1.0);
inline void inc(long long &x, long long y) {
  x += y;
  if (x >= mod) x -= mod;
}
inline void dec(long long &x, long long y) {
  x -= y;
  if (x < 0) x += mod;
}
inline void chmax(long long &x, long long y) {
  if (y > x) x = y;
}
inline void mulm(long long &x, long long y) {
  x *= y;
  if (x >= mod) x -= mod;
}
long long xo(long long i) {
  if ((i & 3) == 0) return i;
  if ((i & 3) == 1) return 1;
  if ((i & 3) == 2) return i + 1;
  return 0;
}
long long a[1000105];
long long rev(long long x) {
  long long m = 0;
  for (long long i = 0; i <= 20; i++)
    if (x & (1 << i)) m = i;
  m++;
  long long g = ((1 << m) - 1);
  return g ^ x;
}
int main() {
  long long n, i, j, k, l, s = 0;
  cin >> n;
  a[0] = 0;
  for (i = n; i > 0; i--) {
    if (a[i] == 0) {
      long long j = rev(i);
      a[i] = j;
      a[j] = i;
      s += 2 * (i ^ j);
    }
  }
  cout << s << endl;
  for (i = 0; i <= n; i++) cout << a[i] << " ";
}
