Problem Description

"X Dragon Balls" is a puzzle mini-game. In the game, there are $n(2|n)$ uniquely numbered dragon balls arranged in a given order in a queue, each with a distinct number. During each operation, two adjacent dragon balls are selected and removed from the queue, then placed at the end of a target queue (which initially is empty, and the order of these two dragon balls remains unchanged). The gaps in the original queue are then removed. This process is repeated until the original queue is empty. It is evident that different decisions lead to different orders in the target queue. Now, you are asked to find the scheme where the target queue has the largest lexicographical order among all possible schemes. You only need to provide the target queue.

For example, when the original dragon ball queue is [1,3,2,4], you can first take out 3 and 2, at which point the target queue is [3,2], and the original queue is [1,4]; then place the remaining two dragon balls into the target queue, resulting in the target queue [3,2,1,4].

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers, representing the numbers of the original dragon ball queue.

Output Format

One line containing $n$ integers.

Sample Input and Output

Sample Input #1

4 
3 1 4 2

Sample Output #1

4 2 3 1

Sample Input #2

6 
6 5 4 1 3 2

Sample Output #2

6 5 4 1 3 2

Notes

For 20% of the data, $n\le10$.
For 60% of the data, $n\le10^3$.
For 100% of the data, $n\le10^5$, and the dragon ball numbers do not exceed n.

见题面 Input 部分

见题面 Output 部分