시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.1 초 32 MB 6 3 3 60.000%

문제

Permutations are intensively studied in mathematics and computer science. Pattern avoiding permutations are of special interest. A permutation p1, p2, . . . , pn of the natural numbers 1, . . . , n is called 3-1-2 pattern avoiding if there are no three indices 1 ≤ i < j < k ≤ n such that pi > pj , pi > pk and pj < pk.

Write a program that computes for a given 3-1-2 pattern avoiding permutation the next 3-1-2 pattern avoiding permutation according to the lexicographic ordering.

입력

The first line of the input contains one integer n (3 ≤ n ≤ 10000). The second line contains n positive integers separated by single spaces, a 3-1-2 pattern avoiding permutation of the natural numbers 1, . . . , n. The input is not the decreasing sequence n, n − 1, . . . , 1.

출력

The first line of the output must contain the 3-1-2 pattern avoiding permutation that follows the input permutation in the lexicographic ordering. The numbers must be separated by a single space.

예제 입력

5
2 4 5 3 1

예제 출력

2 5 4 3 1

힌트