2413번 - 비슷한 순열 분류

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개 주어진다.

첫째 줄에 답을 출력한다.