시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 429 | 159 | 114 | 44.358% |
1부터 n까지의 수들을 중복 없이 나열한 것을 순열이라 한다. 순열이 하나 주어졌을 때, 그 순열과 비슷한 순열들 중에서 제일 작은 것을 구하는 프로그램을 작성하시오.
순열이 비슷하다는 것은, 순열의 각 위치의 수들의 차이가 1 이하인 경우를 말한다. 순열의 크기를 비교할 때는 순열의 제일 앞의 수부터 차례로 비교한다.
예를 들어 1 2 3과 2 1 3은 비슷한 순열이고, 1 2 3과 3 1 2는 1과 3의 차이가 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)이 주어진다. 다음 줄에는 순열의 각 수를 나타내는 자연수가 n개 주어진다.
첫째 줄에 답을 출력한다.
8 8 5 7 3 6 4 2 1
7 4 8 2 6 5 3 1