Get Operations

Array values are distinct. One operation chooses a value x present in the array, places all elements less than x first and then all elements greater than or equal to x, keeping the current relative order within each group. The goal is ascending order: first minimize the number of operations, then take the lexicographically smallest threshold sequence; if the array is already sorted, output −1.

输入格式

The first line contains n; the second line contains the resource values. 1≤n≤50, 1≤value≤10^9, all values distinct.

输出格式

Output the threshold sequence separated by spaces; if no operation is needed, output only −1.

样例 1

输入：

6
6 4 3 5 2 1

输出：

2 3 4 6

样例 2

输入：

5
10 5 14 12 13

输出：

10 14

样例 3

输入：

3
1 2 3

输出：

-1

样例说明

The answers are 2 3 4 6, 10 14 and −1. The source's second example output 14 15 belongs to a different array, and 15 is not in the actual input; this site corrects it to 10 14 according to the given input.