## IOI '09 Practice Task 3 - Museum

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
##### IOI '09 - Plovdiv, Bulgaria

The Plovdiv Museum of Modern Art has an exhibition of ancient Thracian vases. There are 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 th vase, which is 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 , and , such that 's height is exactly the average of the heights of and , either must be positioned to the left of both and , or must be positioned to the right of both and (in other words, may not be positioned between and 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 .

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

#### Sample Input

5

#### Sample Output

3
1
2
5
4

In the above arrangement, is neither between and , nor is it between and . Also, is not between and , and is not between and . Thus, it satisfies the condition of the exhibition organizers.