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