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>
template <typename T, typename U>
inline std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &r) {
  os << "(" << r.first << "," << r.second << ")";
  return os;
}
template <typename T>
inline std::pair<T, T> operator+(const std::pair<T, T> &l,
                                 const std::pair<T, T> &r) {
  return std::make_pair(l.first + r.first, l.second + r.second);
}
template <typename T>
inline std::pair<T, T> operator-(const std::pair<T, T> &l,
                                 const std::pair<T, T> &r) {
  return std::make_pair(l.first - r.first, l.second - r.second);
}
template <typename T, typename U>
inline std::pair<T, T> operator*(const std::pair<T, T> &l, const U &r) {
  return std::make_pair(T(l.first * r), T(l.second * r));
}
template <typename T>
inline T cross(const std::pair<T, T> &l, const std::pair<T, T> &r) {
  return l.first * r.second - l.second * r.first;
}
template <typename T>
inline T dot(const std::pair<T, T> &l, const std::pair<T, T> &r) {
  return l.first * r.first + l.second * r.second;
}
template <typename T>
inline T sq_len(const std::pair<T, T> &l) {
  return l.first * l.first + l.second * l.second;
}
template <typename T>
inline long double len(const std::pair<T, T> &l) {
  return sqrtl(sq_len(l));
}
inline int nxt() {
  int first;
  scanf("%d", &first);
  return first;
}
inline int64_t gcd(int64_t a, int64_t b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
using namespace std;
long long int ans;
void f(int n) {
  if (n < 0) return;
  if (n == 0) {
    printf("0 ");
    return;
  }
  int i, j;
  for (i = 0; (1 << i) <= n; i++)
    ;
  i = 1 << i;
  i--;
  f(i - 1 - n);
  for (j = i - n; j <= n; j++) {
    ans += (i - j) ^ j;
    printf("%d ", i - j);
  }
}
void solve() {
  int n, i, j, k;
  scanf("%d", &n);
  for (i = n; i >= 0;) {
    for (j = 0; (1 << j) <= i; j++)
      ;
    j = (1 << j) - 1;
    for (k = i ^ j; k <= i; k++) ans += j;
    i = (i ^ j) - 1;
  }
  printf("%I64d\n", ans);
  ans = 0;
  f(n);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}
