Previous permutation

Find the previous permutation in lexicographical order.

For the permutation (1, 2, 3, ..., N-1, N), the previous permutation is (N, N-1, ..., 3, 2, 1).

Input

The first line of the input contains the integer (N) ((1 $\le$ N $\le$ 10^5)), representing the number of elements in the permutation. The second line provides the permutation itself.

Output

Output (N) numbers representing the desired permutation.

Examples