Problem Statement

An integer sequence of length $2n$, $X=(X_1,X_2,\dots,X_{2n})$, such that $X_{2i-1}=X_{2i}$ for every $i=1,2,\dots,n$ is called a good sequence.

There is an integer sequence of length $2N$, $A=(A_1,A_2,\dots,A_{2N})$, which contains each integer $i=1,2,\dots,N$ exactly twice.

We want to make $A$ a good sequence by performing the operation of swapping the values of two adjacent terms zero or more times.

Let $K$ be the minimum number of operations we must perform the operation to make $A$ a good sequence. Find the lexicographically smallest good sequence that can be obtained by performing the operations $K$ times on $A$.

What is lexicographical order on sequences? A sequence $S = (S_1,S_2,\ldots,S_{|S|})$ is lexicographically smaller than $T = (T_1,T_2,\ldots,T_{|T|})$ when 1. or 2. below holds. Here, $|S|$ and $|T|$ denotes the lengths of $S$ and $T$, respectively. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$. There is an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ that satisfy both of the following: $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$. $S_i$ is smaller than $T_i$ (as a number).

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $A$ contains each integer $i=1,2,\dots,N$ exactly twice.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_{2N}

Output

Print the lexicographically smallest good sequence that can be obtained by performing the operations $K$ times on $A$, with spaces in between.