406841: GYM102569 F Moving Target

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Moving Targettime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are at the shooting range. There are $$$n$$$ windows in front of you, placed in a line from left to right (the leftmost window has number 1, and the rightmost window — number $$$n$$$). There is a target behind one of the windows. The exact location of the target is unknown, and there is no way to determine it. When you shoot in one of the windows, you win if you hit the target, and if you don't, the target, if it is not already behind the rightmost window, moves one window right.

You have to create a strategy that allows to hit a target in a minimal number of shots.

Input

The input contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of windows.

Output

In the first line output the integer $$$k$$$ ($$$1 \le k \le n$$$) — the minimal number of shots to hit the target for sure.

In the second line output $$$k$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n$$$) — the sequence of window numbers to shot at.

Note that, as you immediately win after hitting the target, there exists a deterministic strategy that allows you to win in a minimal number of shots.

If there are several possible answers, output any of them.

ExamplesInput
2
Output
2
1 2 
Input
3
Output
2
1 3 

加入题单

上一题 下一题 算法标签: