Similar Permutation

A permutation is a sequence containing each integer from 1 to n exactly once. Given a permutation P, find the lexicographically smallest permutation that is similar to P.

Two permutations A and B are similar if |A_i - B_i| <= 1 for every position i. To compare two permutations, compare their elements from left to right; at the first position where they differ, the one with the smaller element is smaller.

For instance, [1, 2, 3] and [2, 1, 3] are similar, while [1, 2, 3] and [3, 1, 2] are not similar because their first elements differ by 2. When n = 3, the permutations in increasing order are [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

The first line contains an integer n (3 <= n <= 50,000).

The second line contains n integers, the elements of the permutation P.

Print the lexicographically smallest permutation that is similar to P.