G. String generator 2
time limit per test
1 second
memory limit per test
13 megabytes
input
stdin
output
stdout

You are given a sequence of integer numbers B. You should find the lexicographically smallest sequence A, consisting of the numbers from B, for which there is no i (1 ≤ i < |A|) such that Ai = Ai + 1. You can use each number from B only once.

Input

The first line of the input contains a single integer number N (1 ≤ N ≤ 106). The second line contains N integer numbers Bi separated by spaces (1 ≤ Bi ≤ 106).

Output

Output a sequence A which satisfies specified conditions. Output  - 1 if such sequence does not exist.

Examples
Input
5
2 3 1 3 1
Output
1 2 3 1 3