#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

The Plovdiv Museum of Modern Art has an exhibition of ancient Thracian vases. There are *N* 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).

## Task

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

## Constraints

1 ≤ N ≤ 2,000 | The number of vases |

## Input

The first and only line contains a singer integer*N*.

## Output

There should be*N*lines, each representing the

*N*positions in the arrangement, in order from left to right. Line

*k*should contain a single integer

*H*, the height of the vase you decided to place on position

_{k}*k*. All

*N*heights should be distinct integers between 1 and

*N*inclusive.

## Sample Input 1

5

## Sample Output 1

3 1 2 5 4

## Explanation for Sample Output 1

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.### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 5 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o museum -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512