Restoration of permutation#2367

Restoration of permutation

2 seconds
64 megabytes
Very hard

Today at school, Christopher learned about sequences and permutations. A permutation of numbers from to is a sequence a_1, \ldots, a_n, where each number from the set appears exactly once.

He found the following definitions particularly interesting: - A descent at position in the permutation \langle a_1, a_2, \ldots, a_n \rangle occurs when a_i > a_{i+1}. - A fixed point at position in the permutation \langle a_1, a_2, \ldots, a_n \rangle is when a_i = i.

Inspired by these concepts, he created a special type of permutation called the Robin permutation.

A permutation A = \langle a_1, a_2, \ldots, a_{2n} \rangle of natural numbers from to is a Robin permutation if it satisfies the following conditions: - has exactly descents, all occurring at odd positions (that is, a_{2i-1} > a_{2i} for all ); - has exactly fixed points.

For instance, the permutation \langle 3, 2, 6, 4, 5, 1 \rangle 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 \langle 3, 2, 6, 4, 5, 1 \rangle results in \langle 3, 6, 1 \rangle \rightarrow \langle 2, 3, 1 \rangle.

Now, Christopher wants to reconstruct a Robin permutation from the transformed permutation.

Input

The first line of the input contains — the number of elements in the transformed permutation (1 \leq n \leq 100000). The second line contains natural numbers representing the transformed permutation.

Output

If no solution exists, output . If a Robin permutation can be constructed, output it. If multiple solutions are possible, any valid Robin permutation may be output.

Examples

Example 1

Loading
Loading