Tree DFS Insertion Game

Alice and Bob are planting trees and playing a game. There are 2n nodes labeled from 1 to 2n. The weights on the nodes form a permutation \(a = (a_1, a_2, \dots, a_{2n})\) of \(\{1, 2, \dots, 2n\}\), where \(a_i\) is the weight on node \(i\).

The game is played as follows:

1. Nodes 1 through n belong to Alice and nodes \(n+1\) through \(2n\) belong to Bob. They agree that node 1 is the root of a tree.
2. Alice determines the parent for each of her nodes (nodes 2 through n). For each node \(i\) (\(2 \le i \le n\)), she must choose a parent from the set \(\{1,2,\dots,i-1\}\).
3. Bob then determines the parent for each of his nodes (nodes \(n+1\) through \(2n\)). For each node \(i\) (\(n+1 \le i \le 2n\)), he may choose a parent from \(\{0,1,2,\dots,i-1\}\). Here, choosing parent 0 means that node \(i\) will not be attached to the tree.
4. After the edges are set, Alice performs a depth-first search (DFS) starting from the root (node 1). When a node is first visited, its weight is appended to a sequence. When visiting any node, the children are visited in increasing order of their node labels.

Both players are strategic. Alice wants the final DFS sequence to be as lexicographically small as possible, while Bob wants it to be as lexicographically large as possible. The lexicographical comparison is defined as follows:

• For any sequence \(a\) of length \(L\), we define \(a_i = -\infty\) for all \(i > L\).
• For two sequences \(a\) and \(b\), we say \(a\) is lexicographically smaller than \(b\) if there exists an index \(i \ge 1\) such that \(a_j = b_j\) for all \(1 \le j < i\) and \(a_i < b_i\).

Assume that both players play optimally. It turns out that no matter how Alice arranges her tree among nodes 1 through n, under the optimal strategies the DFS order of Alice’s nodes is always in increasing order of the labels (i.e. 1, 2, …, n). Bob can attach his nodes to the tree to force his nodes into the DFS order. A careful analysis reveals that Bob's unique best strategy is to attach all his nodes to node \(n\) (which has no child in Alice’s tree). Under these optimal strategies, the DFS will first visit nodes 1, 2, …, n (in that order) and then visit Bob’s nodes in increasing order of their labels \(n+1, n+2, \dots, 2n\).

Therefore, the final DFS sequence will be:

[ (a_1, a_2, \dots, a_n, a_{n+1}, a_{n+2}, \dots, a_{2n}). ]

Your task is to compute and output this sequence.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (1 \(\le n\) \(\le\) 10⁵).
• The second line contains \(2n\) space-separated integers \(a_1, a_2, \dots, a_{2n}\), which form a permutation of \(\{1, 2, \dots, 2n\}\).

outputFormat

Output the final DFS sequence as determined by the optimal strategies. That is, output \(2n\) space-separated integers corresponding to \(a_1, a_2, \dots, a_{2n}\).

sample

1
1 2

1 2