P5462 X Dragon Balls

"X Dragon Balls" is a puzzle mini-game. In the game, there are $n(2|n)$ dragon balls with distinct numbers, arranged in a queue in the given order, and each dragon ball has a number on it. In each operation, choose and take out two **adjacent** dragon balls from the original queue, and put them at the end of the target queue (the target queue is initially empty, and the relative order of these two dragon balls does not change). Then remove the gap in the original queue. Repeat this process until the original queue becomes empty. It is clear that different choices lead to different orders of the target queue. Now you need to find, among all possible operations, the one that makes the target queue lexicographically largest. You only need to output the target queue. For example, when the original queue is [1,3,2,4], you can first take out 3 and 2. Then the target queue becomes [3,2], and the original queue becomes [1,4]. Next, put the remaining two dragon balls into the target queue, and the final target queue is [3,2,1,4].

The first line contains an integer $n$. The next line contains $n$ integers, representing the numbers of the dragon balls in the original queue.

One line with $n$ integers.

For 20% of the testdata, $n \le 10$。 For 60% of the testdata, $n \le 10^3$。 For 100% of the testdata, $n \le 10^5$, and the dragon ball numbers do not exceed $n$。 Translated by ChatGPT 5