IOI '09 - Plovdiv, Bulgaria

The Plovdiv Museum of Modern Art has an exhibition of ancient Thracian vases. There are ~N~ ~(1 \le N \le 2\,000)~ vases total. The first one is a miniature of height 1 centimeter. The second one is of height 2 centimeters; the third one is 3 centimeters tall and so on until the ~N^\text{th}~ vase, which is ~N~ centimeters tall.

Since this is a modern art museum and the vases are ancient, the organizers of the exhibition would like to add a modern, chaotic twist to the presentation of the vases. They have decided to arrange the vases in a line that satisfies the following condition: For any three vases ~A~, ~B~ and ~C~, such that ~B~'s height is exactly the average of the heights of ~A~ and ~C~, either ~B~ must be positioned to the left of both ~A~ and ~C~, or ~B~ must be positioned to the right of both ~A~ and ~C~ (in other words, ~B~ may not be positioned between ~A~ and ~C~ on the line).

Write a program that, given the number of vases, determines a linear arrangement of the vases that satisfies the condition of the exhibition organizers.

Input Specification

The input contains a single line, which in turn contains a single integer: the number of vases ~N~.

The output should contain ~N~ lines, each representing the ~N~ positions in the arrangement, in order from left to right. Line ~k~ should contain a single integer ~H_k~, the height of the vase you decided to place on position ~k~. All ~N~ heights should be distinct integers between ~1~ and ~N~ inclusive.

Sample Input

5

Sample Output

3
1
2
5
4

In the above arrangement, ~3~ is neither between ~2~ and ~4~, nor is it between ~1~ and ~5~. Also, ~2~ is not between ~1~ and ~3~, and ~4~ is not between ~3~ and ~5~. Thus, it satisfies the condition of the exhibition organizers.