409487: GYM103577 M Classroom Reordering

Have you heard the saying that goes "when the cat's away, the mice will play"? Well, that was what happened in classroom 205 of the CyT building. They were in class and suddenly the professor had to leave the classroom for some time. At this moment the $$$n$$$ chairs in the classroom were organized forming a circumference, each chair back to the other.

As soon as the party started, the students rearranged the chairs in some random way. After a while, somebody noticed the professor was coming back to the classroom and they were really afraid of the professor's reaction. That is why they need your help, since you have perfect memory and you remember how the chairs were arranged when the professor left. But you do not have much time, so you advise your classmates to arrange the chairs in such a way that they form a circumference and it is as similar as possible to the way the chairs are currently arranged.

More formally, there are $$$n$$$ chairs, numbered from $$$1$$$ to $$$n$$$. The current arrangement is given by an array $$$a$$$ of $$$n$$$ integers ($$$1 \leq a_i \leq n$$$). If $$$a_i=i$$$ then there is no chair in front of $$$i$$$-th chair, otherwise $$$a_i$$$ is the chair in front of the $$$i$$$-th chair.

You have to find an arrangement $$$b$$$, which is an array of $$$n$$$ distinct integers ($$$1 \leq b_i \leq n$$$), which is as similar as possible to $$$a$$$. Additionally, $$$b$$$ must be a circumference. A circumference has the property that if I start at any chair, and go to the chair in front $$$n$$$ consecutive times, I will visit each of the $$$n$$$ chairs exactly once.

Let $$$l(x,y)$$$ be the longest common prefix of arrangements $$$x$$$ and $$$y$$$, that is, the maximum $$$k$$$ such that $$$x_1=y_1, x_2=y_2, \ldots x_k=y_k$$$. We consider an arrangement $$$x$$$ more similar to $$$a$$$ than arrangement $$$y$$$ if $$$l(x,a) > l(y,a)$$$, or if $$$l(x,a) = l(y,a)$$$ and $$$x$$$ is lexicographically smaller than $$$y$$$.

The first line of input contains one integer: $$$n$$$ ($$$1 \leq n \leq 5\times10^5$$$).

The second line contains $$$n$$$ space separated integers: $$$a_1, a_2, \ldots, a_n$$$.

Print a single line with n space separated numbers: $$$b_1, b_2, \ldots, b_n$$$.

7
3 4 6 5 7 1 2

3 4 6 5 7 2 1

8
3 3 3 1 1 5 7 3

3 1 4 5 6 7 8 2