Kantipa wants to coordinate a dance performance where the dancers sit while dancing. The dance consists of $$$N$$$ dancers sitting in a single row. The stage consists of $$$10^{100}$$$ pre-made slots for the dancers to sit, numbered from $$$1$$$ to $$$10^{100}$$$ from left to right. These slots are equally spaced.
A configuration of the $$$N$$$ dancers is valid if and only if all of the following are satisfied:
There are $$$N$$$ dancers numbered from $$$1$$$ to $$$N$$$. Initially, all $$$N$$$ dancers are sitting on different slots among slots $$$1$$$ through $$$N$$$. In other words, there exists an array $$$P$$$ that's a permutation of $$$[1,2,\ldots,N]$$$ such that dancer $$$i$$$ is initially sitting on slot $$$P_i$$$.
For a permutation $$$P$$$, Kantipa defines the value of $$$f(x)$$$ ($$$0\leq x\leq N-2$$$) as the number of different values of $$$\mathbf{k}$$$ such that Kantipa can rearrange the positions of dancers $$$1$$$ through $$$x$$$ to any slots to make the configuration $$$k$$$-separated, while not changing the positions of dancers $$$x+1$$$ through $$$N$$$.
Find any permutation $$$P$$$ such that the value of $$$f(0)+f(1)+f(2)+\ldots+f(N-2)$$$ is as big as possible! If there are multiple solutions, output any of them.
The only line contains a single integer $$$N$$$ ($$$2 \leq N \leq 300\,000$$$) — the number of dancers.
Print $$$N$$$ integers in one line. The $$$i$$$-th integer is the value of $$$P_i$$$ (the initial position of dancer $$$i$$$). If there are multiple solutions, output any of them.
5
4 2 3 5 1
For $$$f(0)$$$, we can only do nothing, which would make it $$$1$$$-separated, so $$$f(0)=1$$$.
For $$$f(1)$$$, by being able to rearrange the position of dancer $$$1$$$, we can still only make it $$$1$$$-separated, so $$$f(1)=1$$$.
For $$$f(2)$$$, by being able to rearrange the positions of dancers $$$1$$$ and $$$2$$$, not only can we make it $$$1$$$-separated, we can also make it $$$2$$$-separated by moving dancer $$$1$$$ to slot $$$9$$$ and moving dancer $$$2$$$ to slot $$$7$$$, so $$$f(2)=2$$$.
For $$$f(3)$$$, by being able to rearrange the positions of dancers $$$1$$$, $$$2$$$, and $$$3$$$, not only can we make it $$$1$$$-separated and $$$2$$$-separated, we can also make it $$$4$$$-separated by moving dancer $$$1$$$ to slot $$$9$$$, moving dancer $$$2$$$ to slot $$$17$$$, and moving dancer $$$3$$$ to slot $$$13$$$, so $$$f(2)=3$$$.
Therefore, $$$f(0)+f(1)+f(2)+f(3)=7$$$, which is the biggest possible value of this sum for $$$5$$$ dancers.