Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.

For permutation p = p_0, p_1, ..., p_{n}, Polo has defined its beauty — number $(0 \oplus p_{0}) +(1 \oplus p_{1}) + \cdots +(n \oplus p_{n})$.

Expression $x \oplus y$ 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 ≤ 10^6).


-----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

Difficulty: competition

Starter code:

Solutions:
n = int(input())
p = [i for i in range(n + 1)]

k = 1
while(2 * k <= n):
  k *= 2
m = n + 1
while m > 0:
  while k >= m:
    k //= 2
  for i in range(m - k):
    if k - i - 1 >= 0:
      p[k + i], p[k - i - 1] = p[k - i - 1], p[k + i]
  m = k - i - 1

print(n * (n + 1))
print(' '.join(map(str, p)))

n = int(input()) + 1
print(n * n - n)
t = []
k = 1 << 20

while n:
    while k >> 1 >= n: k >>= 1
    t = [(k - 1) ^ i for i in range(k - n, n)] + t
    n = k - n

print(' '.join(map(str, t)))

s = n = int(input()) + 1
t, r = [], list(range(n))[::-1]
k = 2 ** 20

while s:
    while k >= 2 * s: k //= 2
    t = r[n - s: n + s - k] + t
    s = k - s

print(n * n - n)
print(' '.join(map(str, t)))

s = n = int(input()) + 1
t, r = [], list(range(n))[::-1]
k = 2 ** 20

while s:
    while k >= 2 * s: k //= 2
    t = r[n - s: n + s - k] + t
    s = k - s

print(n*(n-1))
print(*t)

import math 
def ones(n): 
    number_of_bits = (int)(math.floor(math.log(n) /
                                math.log(2))) + 1;   
    return [((1 << number_of_bits) - 1) ^ n,(1 << number_of_bits) - 1]; 
n = int(input())
has=[0]*(n+1)
ans=[0]*(n+1)
fin=0
for i in range(n,0,-1):
    if has[i]==0:
        com,fi = ones(i)
#        print(com,fi,i)
        has[com]=1
        fin+=2*fi
        ans[com]=i
        ans[i]=com
print(fin)
print(*ans)