Similar Permutation
Time limit1sMemory limit128 MB
Given a permutation, construct the lexicographically smallest permutation where each position differs from the original by at most 1.
- Level
Medium6 of 10
- Topics
- Greedy, Array, Simulation
- Solved
- No attempts yet
Problem
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].
Input
The first line contains an integer n (3 <= n <= 50,000).
The second line contains n integers, the elements of the permutation P.
Output
Print the lexicographically smallest permutation that is similar to P.