6330: 雷霆闪电

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Special Judge Creator:
Submit:24 Solved:14

Description

小W是一位年轻的军事飞行员,他参加了一场紧急任务,需要摧毁一支藏匿在城市郊外的补给车队。这支车队被发现藏身在一条长长的单行道上,而小W的使命就是使用他的轰炸机精确地摧毁所有敌对补给车,以遏制敌人的威胁。由于敌方部队守卫严密,小W必须在高空中进行轰炸,同时尽可能减少投弹的数量,以确保任务的成功完成。
如上所述,地图是一个1×n的方格道路(编号为1..n),每个方格中都有一辆或多辆补给车。因为飞得很高,小 W 不知道确切的数量和它们的位置。他需要摧毁所有补给车,并且希望用尽可能少的炸弹实现目标。当一辆补给车受到伤害时,它会立即向相邻的道路移动一步(在n单元的补给车只能移动到n-1单元,在1单元的补给车只能移动到2号单元)。如果补给车受到两次攻击,则认为被摧毁了。
补给车只有在第一次被攻击时才会移动,不受到攻击不会移动。

Input

一行,一个整数n(2 ≤ n ≤ 100000),表示地图的大小。

Output

第一行,整数m,表示摧毁所有补给车所需的最少炸弹数量。
第二行,m个整数k1,k2,...,km,数字ki表示第i枚炸弹投在ki单元。
如果有多个答案,输出其中一个即可。

Sample Input Copy

输入1 
2
输入2 
3

Sample Output Copy

输出1 
3
2 1 2
输出2 
4
2 1 3 2

HINT

【数据规模】
20%的数据,n ≤ 15;
100%的数据,n ≤ 100000。