小企鹅波罗喜欢排列。但最重要的是,他喜欢从 0 到 n(含)的整数排列。
对于排列 p = p0, p1, ..., pn,Polo 定义了它的美 - 数字 $$(0\oplus p_{0})+(1\oplus p_{1})+\cdots+(n\oplus p_{n})$$。
表达式 $$x \oplus y$$ 表示对数字 x 和 y 进行按位排除“OR”的运算。此操作存在于所有现代编程语言中,例如,在 C++ 和 Java 语言中,它表示为“^”,在 Pascal 中表示为“xor”。
帮助他在0到n的所有整数排列中找到最美丽的排列。
输入
单行包含一个正整数 n (1 ≤ n ≤ 106)。
输出
在第一行打印整数 m 的最大可能的美感。在第二行中打印从 0 到 n 的任意整数排列,美度等于 m。
如果有多个合适的排列,您可以打印其中任何一个。
示例
输入 #1
4
输出 #1
20 0 2 1 4 3