401367: GYM100418 G String generator 2

Memory Limit:13 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. String generator 2time limit per test1 secondmemory limit per test13 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput
5
2 3 1 3 1
Output
1 2 3 1 3 

加入题单

上一题 下一题 算法标签: