409980: GYM103886 G Vacation

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Vacationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ariel is on a vacation where he must visit $$$n$$$ locations famous for their cereal, numbered $$$1 \dots n$$$.

He will visit all the locations in some order, where the $$$i$$$th location he visits is $$$a_i$$$.

Therefore, his order of visiting locations forms a permutation of length $$$n$$$. Note that a permutation of length $$$n$$$ is a sequence containing every number from $$$1 \dots n$$$ exactly once.

Ariel thinks an amazing permutation is one where there are no indices $$$(i, j, k)$$$ where ($$$1 \le i < j < k \leq n$$$) such that $$$j - i = k - j$$$ and $$$a_j - a_i = a_k - a_j$$$.

Find a permutation of $$$1 \dots n$$$ that satisfies this (the $$$i$$$th number is the $$$i$$$th location Ariel visits).

Input

A single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$).

Output

A single line containing a space separated permutation of $$$1 \dots n$$$ such that Ariel has an amazing vacation.

Any output satisfying the above constraints will be accepted.

ExamplesInput
4
Output
1 2 4 3
Input
10
Output
10 1 7 8 2 4 9 5 6 3
Note

If we take the first sample case output, no three indices validate the above condition.

For example, if $$$(i, j, k)$$$ = $$$(1, 2, 4)$$$, $$$2 - 1 \neq 4 - 2$$$.

Another example would be $$$(i, j, k)$$$ = $$$(1, 2, 3)$$$. Although, $$$j - i = k - j$$$ since $$$2 - 1 = 3 - 2$$$, $$$a_j - a_i \neq a_k - a_j$$$ since $$$4 - 2 \neq 2 - 1$$$.

Problem Credits: Ariel Shehter

加入题单

上一题 下一题 算法标签: