Restoration of permutation
Today at school, Christopher learned about sequences and permutations. A permutation of numbers from 1 to n is a sequence a_1, ..., a_n, where each number from the set appears exactly once.
He found the following definitions particularly interesting:
A descent at position i in the permutation <a_1, a_2, ..., a_n> occurs when a_i > a_{i+1}.
A fixed point at position i in the permutation <a_1, a_2, ..., a_n> is when a_i = i.
Inspired by these concepts, he created a special type of permutation called the Robin permutation.
A permutation A = <a_1, a_2, ..., a_2n> of 2n natural numbers from 1 to 2n is a Robin permutation if it satisfies the following conditions:
A has exactly n descents, all occurring at odd positions (i.e., a_{2i-1} > a_2i < a_{2i+1} for all i).
A has exactly n fixed points.
For instance, the permutation <3, 2, 6, 4, 5, 1> is a Robin permutation.
Christopher shared his discovery with Rabbit, who then proposed a transformation: remove all fixed points from the sequence and transform the remaining numbers into a permutation by replacing each number with the count of elements that do not exceed it in the permutation. For example, transforming the permutation <3, 2, 6, 4, 5, 1> results in <3, 6, 1> → <2, 3, 1>.
Now, Christopher wants to reconstruct a Robin permutation from the transformed permutation.
Input
The first line of the input contains n - the number of elements in the transformed permutation (1 ≤ n ≤ 100000). The second line contains n natural numbers representing the transformed permutation.
Output
If no solution exists, output -1. If a Robin permutation can be constructed, output it. If multiple solutions are possible, any valid Robin permutation may be output.