조건을 만족하는 가장 앞선 수열

길이가 n인 수열 S가 주어진다. S는 1부터 n까지의 모든 정수를 한 번씩 포함하는 순열이다.

다음 조건을 모두 만족하는 수열 T 중 사전순으로 가장 앞서는 수열을 구하라.

1. T도 1부터 n까지의 모든 정수를 한 번씩 포함하는 순열이다.
2. 모든 i에 대해 |T_i - S_i| <= 1이다.

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

다음 n개 줄에는 수열 S를 이루는 수가 순서대로 한 개씩 주어진다.

조건을 만족하는 수열 중 사전순으로 가장 앞서는 수열 T를 n개의 줄에 걸쳐 순서대로 출력한다.