Maximizing the Lock Paralysis Time

A special password lock consists of a chain of n nodes (the value of n is fixed by the lock’s nameplate). Each node can hold at most one atom. Initially, all n atoms with labels 1,2,...,n are placed one per node in some order. The charge of the i-th atom is defined as \(i! = 1 \times 2 \times 3 \times \cdots \times i\). There is also a timer b (in seconds) which is initially \(0\).

Once the lock is heated, the following events occur cyclically and sequentially until a termination condition is reached:

1. Removal: Remove any atom located at either end of the chain (i.e. at node \(1\) and node \(n\)). These removed atoms no longer affect subsequent events. (Note that the chain always has n nodes.)
2. Termination check:
   • If there is at most one atom remaining in the chain (possibly 0), the termination condition is met and the lock becomes paralyzed. (In this round the timer b is not incremented.)
   • Otherwise, increase the timer b by \(1\).
3. Direction assignment: For each remaining atom placed at some node, determine its temporary movement direction (this assignment is reset in each cycle):
   • Let \(x\) be the sum of the charges (factorials) of all atoms located to its left.
   • Let \(y\) be the sum of the charges of all atoms located to its right.
   • If \(x y\) then it is marked to move right. It can be proved that \(x \neq y\) always holds.
4. Movement: All remaining atoms move one node in the direction they were marked.

Krjt has read the value of \(n\) from the nameplate. He defines the paralysis time of the lock as the value of \(b\) when the system terminates. To maximize the security of the lock, he wants to maximize this paralysis time. Your task is to help him choose an initial permutation of the n atoms that achieves this goal.

Note: It turns out that one optimal strategy is to simply arrange the atoms in increasing order from \(1\) to \(n\). In this problem you only need to output one such optimal arrangement.

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of atoms (and nodes in the chain).

outputFormat

Output a permutation of the integers \(1,2,...,n\) separated by spaces. This ordering is the initial arrangement of the atoms that maximizes the lock’s paralysis time.

Note: It has been shown that the increasing order (i.e. 1 2 3 ... n) is optimal.

sample

4

1 2 3 4