← 返回题目列表

Codeforces · 288/C

C. Polo 企鹅和异或运算

中文机器翻译题面 查看原题

小企鹅波罗喜欢排列。但最重要的是,他喜欢从 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