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
from sys import stdout
def main():
    n = int(raw_input())
    a = [-1] * (n + 1)
    s = 0
    c = [1]
    while n >= c[-1]: c.append(c[-1] * 2)
    c = [x - 1 for x in reversed(c)]
    for i in xrange(n, -1, -1):
        if a[i] != -1: continue
        for x in c:
            if x-i <= n and a[x-i] == -1:
                a[x-i] = i
                a[i] = x-i
                s += x + x
                break
    print s
    stdout.write(' '.join(map(str, a)))
    print
main()
