← 返回题目列表

Codeforces · 877/C

C. Slava 和坦克

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

Slava 玩他最喜欢的游戏“和平闪电”。现在他正在一个非常具体的地图上驾驶轰炸机。

形式上,地图是一个大小为 1 × n 的方格域,其单元格编号为 1 到 n,每个单元格中可以有一个或多个坦克。斯拉瓦不知道坦克的数量和位置,因为他飞得很高,但他可以在任何牢房投下炸弹。该牢房中的所有坦克都将被损坏。

如果坦克第一次受到伤害,它会立即移动到相邻单元格之一(单元格n中的坦克只能移动到单元格n-1,单元格1中的坦克只能移动到单元格2)。如果坦克第二次受到伤害,它就会被视为被摧毁,并且不再移动。坦克仅在第一次损坏时才会移动,它们不会自行移动。

帮助 Slava 使用尽可能少的炸弹摧毁所有坦克。

输入

第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 地图的大小。

输出

在第一行打印 m — Slava 摧毁所有坦克所需的最少炸弹数量。

在第二行打印 m 个整数 k1, k2, ..., km。数字 ki 表示第 i 个炸弹应该投在 ki 单元格上。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

2

输出 #1

3
2 1 2

输入 #2

3

输出 #2

4
2 1 3 2