Background

Update on 2025/5/11: We added a visualization tool in the attachments.

Update on 2025/5/26: The visualization tool has been updated.

This is a problem from FAOI in the year $2027$. It is a traditional problem with an SPJ.

After krjt was JC by $160$ people last time, he switched to a "quantum combination lock" and used it to lock his laptop bag. If you cannot open the lock, you cannot take the laptop out of the bag. In theory, once krjt forgets the password, even the person who made the lock cannot open it.

However, this lock is not unbreakable. One day, krjt suddenly became very interested in chemistry. He picked up the lock and heated it over an alcohol lamp, and then found that: In a high-temperature environment, the arrangement of atoms inside the lock (strictly speaking, "ions", same below) becomes unstable, which will cause it to break down.

Problem Description

krjt found the manual of the combination lock:

In the combination lock, there is a chain of length $n$ (cannot be changed; the specific value of $n$ can be found on the nameplate). There are $n$ nodes on the chain. Each node can store at most one atom. Initially, atoms $1,2,\ldots,n$ are stored in it in some order (the user may adjust it), with one atom per node.

Define the charge of atom $i$ as $i!=1 \times 2\times 3 \times \ldots \times i$.

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

After the lock is heated, the following events repeat in order until the termination condition is met:

1. The atoms at both ends of the chain are removed (this does not shorten the chain), and they no longer affect subsequent events.
2. Check the termination condition:
   • If at this time there are no more than $1$ atom left in the chain (it can also be $0$), then the termination condition is met, and the lock breaks down (the value of $b$ will not be increased by $1$ at this time).
   • Otherwise, increase the value of $b$ by $1$.
3. Assign a movement direction to each atom (the assigned direction is temporary, only effective once, and will be reset before the next assignment):
   • Compute the sum of charges of all atoms to its left, and denote the result as $x$.
   • Compute the sum of charges of all atoms to its right, and denote the result as $y$.
   • If $x<y$, then the direction is "to the left".
   • If $x>y$, then the direction is "to the right".
   • It can be proven that $x \ne y$.
4. All atoms move one edge along their assigned directions to the adjacent node.

In addition, krjt read the value of $n$ from the nameplate.

krjt defines the time for the lock to break down as the value of $b$ when it breaks down. Of course, krjt hopes the lock is as secure as possible, so he wants to maximize the breakdown time.

To avoid more people JC krjt again, please answer: how should he arrange the initial order of the $n$ atoms in the lock?

Input Format

One line with one positive integer $n$.

Output Format

One line with $n$ positive integers, a permutation of $1 \sim n$, representing the arrangement you design for krjt. Output the IDs of the $n$ atoms in order from left to right (or from right to left; it can be proven that their breakdown times are the same).

There may be multiple correct answers. Output any one of them.

1

1

2

1 2

3

2 1 3

4

4 2 3 1

5

5 4 1 2 3

6

2 4 5 1 6 3

Hint

Explanation of the samples:

For the $6$ samples, the breakdown times are $0,0,0,1,1,2$ seconds.

In fact, by enumeration it can be seen that when $n \le 6$, outputting any permutation of $1 \sim n$ will get AC.

Below is a simulation for sample $6$. In the chain description:

• $0$ means the node is empty.
• $i$ means the node contains atom $i$.
• $(x,y)$ is the computed result.

1. The initial chain is $\color{blue}2-4-5-1-6-3$.
2. Initially, $b$ is $0$.
3. The atoms at both ends are removed, and the chain becomes $\color{blue}0-4-5-1-6-0$.
4. $b$ increases to $1$.
5. Compute. For the $4$ atoms (from left to right), the results 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. According to the results, the left $3$ atoms ($4,5,1$) move left, and the rightmost atom ($6$) moves right, and the chain becomes $\color{blue}4-5-1-0-0-6$.
7. The atoms at both ends are removed, and the chain becomes $\color{blue}0-5-1-0-0-0$.
8. $b$ increases to $2$.
9. Compute. For the $2$ atoms (from left to right), the results are $(\color{red}0\color{black},1),(120,\color{red}0\color{black})$.
10. According to the results, the left atom ($5$) moves left, and the right atom ($1$) moves right, and the chain becomes $\color{blue}5-0-0-1-0-0$.
11. The atoms at both ends are removed, and the chain becomes $\color{blue}0-0-0-1-0-0$.
12. At this time, only $1$ atom ($1$) remains in the chain, so the process ends and the lock breaks down.

In summary, the breakdown time for sample $6$ is $2$ seconds.

This problem has $100$ test points, with $n=1,2,\ldots,100$, $1$ point each.

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

Input Format

One line with one positive integer $n$.

Output Format

One line with $n$ positive integers, a permutation of $1 \sim n$, representing the arrangement you design for krjt. Output the IDs of the $n$ atoms in order from left to right (or from right to left; it can be proven that their breakdown times are the same).

There may be multiple correct answers. Output any one of them.

Hint

Explanation of the samples:

For the $6$ samples, the breakdown times are $0,0,0,1,1,2$ seconds.

Actually, by enumeration it can be seen that when $n \le 6$, outputting any permutation of $1 \sim n$ will get AC.

Below is a simulation for sample $6$. In the chain description:

• $0$ means the node is empty.
• $i$ means the node contains atom $i$.
• $(x,y)$ is the computed result.

1. The initial chain is $\color{blue}2-4-5-1-6-3$.
2. Initially, $b$ is $0$.
3. The atoms at both ends are removed, and the chain becomes $\color{blue}0-4-5-1-6-0$.
4. $b$ increases to $1$.
5. Compute. For the $4$ atoms (from left to right), the results 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. According to the results, the left $3$ atoms ($4,5,1$) move left, and the rightmost atom ($6$) moves right, and the chain becomes $\color{blue}4-5-1-0-0-6$.
7. The atoms at both ends are removed, and the chain becomes $\color{blue}0-5-1-0-0-0$.
8. $b$ increases to $2$.
9. Compute. For the $2$ atoms (from left to right), the results are $(\color{red}0\color{black},1),(120,\color{red}0\color{black})$.
10. According to the results, the left atom ($5$) moves left, and the right atom ($1$) moves right, and the chain becomes $\color{blue}5-0-0-1-0-0$.
11. The atoms at both ends are removed, and the chain becomes $\color{blue}0-0-0-1-0-0$.
12. At this time, only $1$ atom ($1$) remains in the chain, so the process ends and the lock breaks down.

In summary, the breakdown time for sample $6$ is $2$ seconds.

This problem has $100$ test points, with $n=1,2,\ldots,100$, $1$ point each.

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

Translated by ChatGPT 5