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: MEDIUM_HARD
Tags: Mathematics

Implementation

Starter code:

Solutions:
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)))


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from math import sqrt, ceil, floor, factorial, gcd, log2, log10
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import heappush, heappop, heapify
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
s = n = getInt() + 1
(lst, new) = ([], list(range(n))[::-1])
k = 2 ** 20
while s:
	while k >= 2 * s:
		k //= 2
	lst = new[n - s:n + s - k] + lst
	s = k - s
print(n * (n - 1))
for i in lst:
	output(i)


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


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)
		has[com] = 1
		fin += 2 * fi
		ans[com] = i
		ans[i] = com
print(fin)
print(*ans)


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


import sys
from math import gcd, sqrt, ceil
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
from itertools import permutations
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = set()
	sa.add(n)
	while n % 2 == 0:
		sa.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.add(i)
			n = n // i
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def debug(n):
	l = [i for i in range(n + 1)]
	z = permutations(l)
	maxi = 0
	for i in z:
		fin = 0
		for j in range(n + 1):
			fin += j ^ i[j]
		maxi = max(maxi, fin)
	return maxi
n = int(input())
hash = defaultdict(int)
ans = [0] * (n + 1)
seti = set()
for i in range(n, 0, -1):
	if i not in seti:
		z1 = i ^ int('1' * len(bin(i)[2:]), 2)
		seti.add(z1)
		ans[z1] = i
		ans[i] = z1
fin = 0
for i in range(n + 1):
	fin += i ^ ans[i]
print(fin)
print(*ans)


import math

def solve():
	(n,) = map(int, input().split())
	top = 1
	while top <= n:
		top *= 2
	top -= 1
	ans = [0] * (n + 1)
	i = n
	cur = n
	while i > 0:
		if top - i > cur:
			cur = i
			top = 1
			while top <= cur:
				top *= 2
			top -= 1
		ans[i] = top - i
		ans[top - i] = i
		i -= 1
	score = 0
	if n % 2 == 1:
		ans[top] = 0
		ans[0] = top
	for i in range(n + 1):
		score += ans[i] ^ i
	print(score)
	print(*ans)
t = 1
for _ in range(t):
	solve()