조건을 만족하는 가장 앞선 수열
면접 대비시간 제한1초메모리 제한128 MB
순열 S가 주어질 때 각 원소가 S의 대응 원소와 최대 1 차이가 나도록 하는 사전순으로 가장 작은 순열 T를 구합니다.
문제
길이가 n인 수열 S가 주어진다. S는 1부터 n까지의 모든 정수를 한 번씩 포함하는 순열이다.
다음 조건을 모두 만족하는 수열 T 중 사전순으로 가장 앞서는 수열을 구하라.
T도1부터n까지의 모든 정수를 한 번씩 포함하는 순열이다.- 모든
i에 대해|T_i - S_i| <= 1이다.
입력
첫째 줄에 수열의 길이 n이 주어진다. (3 <= n <= 50,000)
다음 n개 줄에는 수열 S를 이루는 수가 순서대로 한 개씩 주어진다.
출력
조건을 만족하는 수열 중 사전순으로 가장 앞서는 수열 T를 n개의 줄에 걸쳐 순서대로 출력한다.