|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|0.1 초||32 MB||87||24||22||39.286%|
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