Eric wants to visit all ~N~ of his friends. Each friend lives at house ~i~, labelled from ~1~ to ~N~. Each house is separated by a single kilometre, meaning that the distance between house ~i~ and house ~j~ would be ~\left | i-j \right |~. He decides to be a "cool kid", and not travel a certain distance more than once.
For example, if there are 3 houses, he could start at the third house, proceed to the first house, and visit the second house last, with travel distances of ~[2, 1]~.
Eric must visit all of the ~N~ houses. Can you output a sequence that Eric can follow, such that he visits all ~N~ houses and never travels the same distance twice?
Subtask 1 [30%]
~2 \le N \le 10~
Subtask 2 [70%]
~2 \le N \le 10^5~
The first and only line of input will contain an integer ~N~, the number of houses Eric needs to visit. The houses are labelled from ~1~ to ~N~.
You are to output a sequence of houses that matches the constraints stated in the problem description, each house separated by a space.
Sample Input 1
Sample Output 1
1 3 2
Sample Explanation 1
For the first sample, he could also travel from house ~3~ to ~1~, and then ~1~ to ~2~ as stated in the problem description.
Sample Input 2
Sample Output 2
Sample Explanation 2
In the second sample, he could also travel from ~1~ to ~2~.