IOI '09 - Plovdiv, Bulgaria

Museum

The Plovdiv Museum of Modern Art has an exhibition of ancient Thracian vases. There are N (1 ≤ N ≤ 2000) 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^th vase, which is N centimeters tall.

Since this 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

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.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 16, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)