### 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)

It's quiet in here...