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
n = int(raw_input())

lst2 = ['0', '0b1', '0b11', '0b111', '0b1111', '0b11111', '0b111111', '0b1111111', '0b11111111', '0b111111111', '0b1111111111', '0b11111111111', '0b111111111111', '0b1111111111111', '0b11111111111111', '0b111111111111111', '0b1111111111111111', '0b11111111111111111', '0b111111111111111111', '0b1111111111111111111', '0b11111111111111111111']
zero = 0

result = 0
result2 = ''

if n%2 == 0:
    lst = [0]*(n + 1)
    for i in range(n, 0, -1):
        if lst[i] == 0:
            binary = bin(i)
            opposite = int(binary, 2)^int(lst2[len(binary) - 2], 2)
            if opposite == 0:
                opposite = int('0b1' + '0'*(len(binary) - 2), 2)
            binary = int(binary, 2)
            lst[binary] = opposite
            lst[opposite] = binary
        result += i^lst[i]

else:
    lst = [None]*(n + 1)
    for i in range(n, -1, -1):
        if lst[i] == None:
            binary = bin(i)
            opposite = int(binary, 2)^int(lst2[len(binary) - 2], 2)
            if opposite == 0 and zero == 0 and int('0b1' + '0'*(len(binary) - 2), 2) < n:
                opposite = int('0b1' + '0'*(len(binary) - 2), 2)
            else:
                zero = 1
            binary = int(binary, 2)
            lst[binary] = opposite
            lst[opposite] = binary
        result += i^lst[i]


print result
print ' '.join(map(str, lst))
