Every angel loves beauty, which is why I understand your preciousness
---Singing a song for you

Problem Description

There is a chain of length $n$ inside the lock, with each node storing an atom and the charge of each atom being $i!$. When the lock is heated, the following steps are repeated until there is at most one atom left on the chain:

1. Remove the atoms at both ends of the chain.
2. Check if the termination condition is met. If there is one or zero atoms left in the chain, the lock is paralyzed, and heating stops. Otherwise, the timer $b$ is incremented by $1$.
3. Determine the direction of movement for each atom: compute the sum of charges of atoms to its left $x$ and the sum of charges of atoms to its right $y$. If $x < y$, the direction is left; otherwise, it is right.
4. Each atom moves one position in its determined direction.

YYD wants to maximize the paralysis time $b$ of the lock and needs to plan the initial arrangement of atoms.

Input Format

A single line containing a positive integer $n$.

Output Format

A single line containing $n$ positive integers, representing your planned initial arrangement of atoms.

Sample

Input #1:

1

Output #1:

1

Input #2:

2

Output #2:

1 2

Input #3:

3

Output #3:

2 1 3

Input #4:

4

Output #4:

4 2 3 1

Input #5:

5

Output #5:

5 4 1 2 3

Input #6:

6

Output #6:

2 4 5 1 6 3

Hint

For $n \le 6$, all permutations of $1 \sim n$ are correct answers. For larger $n$, explore arrangements that maximize the paralysis time.

Constraints

For 100% of the data, $n \le 10^{5}$ Time limit is $2000ms$