Problem Background

This is a problem from FAOI in the year 2027, a submission-answer problem with a special judge, but it also allows code submissions.

Since krjt was "JC" by 160 people last time, he has switched to a "quantum password lock" and used it to lock his laptop bag. Without unlocking the password lock, he cannot retrieve his laptop from the bag. Theoretically, if krjt forgets the password, even the creator of the lock cannot open it.

However, this lock is not impregnable. Under high temperatures, the arrangement of atoms (strictly speaking, "ions") inside the lock becomes unstable, leading to its paralysis.

Problem Description

krjt has obtained the instruction manual for the password lock:

In the password lock, there is a chain of length $n$ (cannot be changed, the specific value of $n$ is indicated on the lock's nameplate). The chain has $n$ nodes, and each node can hold at most one atom. Initially, atoms numbered $1, 2, \ldots, n$ are stored in these nodes in a user-adjustable order, with one atom per node.

Define the charge of the $i$-th atom as $i!$.

There is a timer $b$ (in seconds) with an initial value of $0$.

After the password lock is heated, the following events occur in a loop until the termination condition is met:

1. The atoms at both ends of the chain are removed (this does not shorten the chain) and no longer affect subsequent events;
2. Check the termination condition:
   - If there are no more than $1$ atom(s) (or even $0$ atoms) left in the chain, the termination condition is met, and the password lock is paralyzed (the value of the timer $b$ does not increase by $1$ at this time);
   - Otherwise, increase the value of the timer $b$ by $1$.
3. Assign a movement direction to each atom (the assigned direction is temporary, effective only once, and will be reset before the next assignment):
   - Calculate the sum of the charges of all atoms to its left, denoted as $x$;
   - Calculate the sum of the charges of all atoms to its right, denoted as $y$;
   - If $x < y$, assign the direction as "left";
   - If $x > y$, assign the direction as "right";
   - It can be proven that $x \neq y$.
4. All atoms move one edge distance in the assigned direction to the adjacent node.

Additionally, krjt has read the value of $n$ from the nameplate.

krjt defines the paralysis time of the password lock as the value of $b$ when it is paralyzed. Naturally, krjt wants the password lock to be as secure as possible, so he aims to maximize the paralysis time of the password lock.

To prevent more people from "JC" krjt, how should he arrange the initial order of the $n$ atoms in the password lock?

Input Format

A single line containing a positive integer, $n$.

Output Format

A single line containing $n$ positive integers, a permutation of $1 \sim n$, representing the arrangement plan you have devised for krjt: output the numbers of the $n$ atoms from left to right (or right to left, it can be proven that their paralysis times are equal).

There may be multiple answers; output one valid solution.

Note: Unlike many other submission-answer problems, this problem does not provide a data file (please input $n = 1, 2, \ldots, 100$ manually), and your answer must be optimal to AC, otherwise, you will not receive points.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

2

Sample Output #2

1 2

Sample Input #3

3

Sample Output #3

2 1 3

Sample Input #4

4

Sample Output #4

4 2 3 1

Sample Input #5

5

Sample Output #5

5 4 1 2 3

Sample Input #6

6

Sample Output #6

2 4 5 1 6 3

Notes

Sample explanations:

The paralysis times for the 6 samples are $0, 0, 0, 1, 1, 2$ seconds respectively.

In fact, enumeration shows that for $n \le 6$, any permutation of $1 \sim n$ will AC.

Below is a simulation for Sample #6. In the chain description:

• $0$ indicates an empty node;
• $i$ indicates the node contains the $i$-th atom;
• $(x, y)$ represents the calculation results.

1. Initial chain is $\color{blue}2-4-5-1-6-3$;
2. $b$ starts at $0$;
3. Atoms at both ends are removed, chain becomes $\color{blue}0-4-5-1-6-0$;
4. $b$ increases to $1$;
5. Calculate, results for $4$ atoms (left to right) are $(\color{red}0\color{black}, 841), (\color{red}24\color{black}, 721), (\color{red}144\color{black}, 720), (145, \color{red}0\color{black})$;
6. Based on results, the left $3$ atoms ($4, 5, 1$) move left, the rightmost atom ($6$) moves right, chain becomes $\color{blue}4-5-1-0-0-6$;
7. Atoms at both ends are removed, chain becomes $\color{blue}0-5-1-0-0-0$;
8. $b$ increases to $2$;
9. Calculate, results for $2$ atoms (left to right) are $(\color{red}0\color{black}, 1), (120, \color{red}0\color{black})$;
10. Based on results, the left atom ($5$) moves left, the right atom ($1$) moves right, chain becomes $\color{blue}5-0-0-1-0-0$;
11. Atoms at both ends are removed, chain becomes $\color{blue}0-0-0-1-0-0$;
12. At this point, only $1$ atom ($1$) remains in the chain, reaction ends, password lock is paralyzed.

In summary, the paralysis time for Sample #6 is $2$ seconds.

This problem allows answer submission.

There are $100$ test cases with $n = 1, 2, \ldots, 100$, each worth $1$ point.

For $100\%$ of the data, $1 \le n \le 100$.

Hint 1: If you encounter a UKE, please contact the problem setter or administrator.

Hint 2: The range of $n$ is limited by the evaluation restrictions of Luogu; otherwise, it could be larger.

Hint 3: When submitting answers, the value of $n$ should match the test case number.

Hint 4: This problem can be treated as a traditional problem; submitting answers is just for convenience in tabulation.

Hint 5: The samples are manually crafted, not the result of the std's execution.

Hint 6: There are $6$ sample points, make sure to get them all!

见题面 Input 部分

见题面 Output 部分