Permutations are intensively studied in mathematics and computer science. Pattern avoiding permutations are of special interest. A permutation p₁, p₂, . . . , p_n 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 p_i > p_j , p_i > p_k and p_j < p_k.</p>

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