비슷한 순열

1부터 n까지의 정수를 중복 없이 한 번씩 나열한 수열을 순열이라고 한다. 순열 P가 주어진다. P와 비슷한 순열 중 사전순으로 가장 작은 순열을 구하시오.

두 순열 A와 B가 비슷하다는 것은 모든 위치 i에 대해 |A_i - B_i| <= 1이 성립한다는 뜻이다. 두 순열의 크기는 앞에서부터 차례대로 비교하며, 처음으로 다른 위치의 수가 더 작은 쪽이 더 작다.

예를 들어 [1, 2, 3]과 [2, 1, 3]은 비슷하지만, [1, 2, 3]과 [3, 1, 2]는 첫 번째 위치의 차이가 2이므로 비슷하지 않다. n = 3일 때 순열을 작은 순서대로 나열하면 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]이다.

첫째 줄에 정수 n(3 <= n <= 50,000)이 주어진다.

둘째 줄에 순열 P의 원소를 나타내는 정수 n개가 공백으로 구분되어 주어진다.

첫째 줄에 P와 비슷한 순열 중 사전순으로 가장 작은 순열을 공백으로 구분해 출력한다.