409503: GYM103585 J Apple Tree Beauty

Ada is in charge of grooming the $$$n$$$ apple trees lined up at the front row of the orchard in order to win the most beautiful orchard award.

Sydney, the judge of the contest and once a competitive programmer, has a very particular scheme to calculate the beauty of the row. The leftmost tree in the row has index $$$0$$$, the tree immediately to its right has index $$$1$$$, and so on and so forth until the $$$n$$$th tree which has index $$$n - 1$$$. If the $$$i$$$th tree has $$$a_i$$$ apples then the beauty $$$b$$$ of the row is determined by:

$$$$$$ b = \Sigma_{i = 0}^{n - 1} \left(i \oplus a_{i}\right) $$$$$$

However, Sydney is extra quirky so she will immediately disqualify any row of apple trees that either has two trees with the same number of apples on them or if a tree has more than $$$n - 1$$$ apples (a tree is allowed to have $$$0$$$ apples). Ada figures out that the assignment of the number of apples to the $$$n$$$ trees must be a permutation of the integers from $$$0$$$ to $$$n - 1$$$ (inclusive).

Ada is stressed because there are far too many possible permutations to calculate by hand and she really wants to win this contest. To make sure there is no chance of Ada losing, help her by calculating the maximum beauty score possible for the row of $$$n$$$ trees and the assignments of the number of apples for each tree that allows for that score.

Note: The $$$c \oplus d$$$ operation refers to the bitwise exclusive or operation where the $$$i$$$th bit of the result is a $$$1$$$ if $$$c$$$ and $$$d$$$ do not have the same $$$i$$$th bit (and $$$0$$$ otherwise). You can calculate this with the ^ operation in languages like Java, C++, and Python.

The first and only line of input contains a single positive integer $$$n$$$ ($$$2 \leq n \leq 10^{6}$$$) representing the number of trees in the row of the orchard.

In the first line, output the maximum possible beauty of the row.

In the second line, output any space-separated permutation $$$p$$$ of the numbers from $$$0$$$ to $$$n - 1$$$ (inclusive) such that if the $$$i$$$th tree in the row was left with $$$p_i$$$ apples, the overall beauty of the row would be equal to the number you printed in the first line.

5

20
0 2 1 4 3

In the first test case, the beauty of the row would be equal to $$$0 \oplus 0 + 1 \oplus 2 + 2 \oplus 1 + 3 \oplus 4 + 4 \oplus 3 = 20$$$ which is the same as the first number printed (trying all other permutations, we see we can't do better than $$$20$$$).