在某一条线段区域上出现了若干坦克,坐标为1到n(保证n>1)。之所以说坐标是1到n,是因为我们也不知道坦克在哪,只知道每一辆都是在1到n闭区间的某个整数点上。
最开始坦克静止在自己的初始点上。现在你可以选若干点开始轰炸。
你轰炸的点x上如果有一辆没有被轰炸过的坦克,你的攻击会使这个坦克受损,并且这辆坦克会向x-1或者x+1两点逃窜,当然如果它在x=1处被轰炸,它就只能向x=2处逃窜,x=n的时候同理;如果你轰炸的点上有一辆受损的坦克,你的攻击会使这个坦克被销毁,此时坦克就不会再移动了。
现在给出线段的长度n,问你需要至少多少次轰炸才能让所有坦克都被销毁,也就是任意位置的坦克、无论逃窜到何处,都需要被轰炸两次。并输出一个合理的轰炸方案。
包括一行,一个整数n如题。
输出两行,第一行一个整数m,表示你需要m次轰炸。
第二行m个数,表示这m次轰炸你选择的轰炸位置。
2
3
1 2 1
3
4
2 1 3 2
对于样例1,在两个位置都可能有坦克,轰炸1之后,2处可能有完整的坦克和受损的坦克,在轰炸2之后,2处不会有未被销毁的坦克,而1处可能会有2处逃窜来的受损坦克,所以需要再轰炸1一次。一共三次。当然,如果你选择轰炸2 1 2也是正确的答案。
对于样例2,在2处轰炸后只会在1、3处有坦克,对13轰炸后,只会在2处有受损的坦克,再对2进行轰炸。一共四次。
保证2≤n≤100000。