You are given a permutation of the first N natural numbers. Find the next one in the lexicographic order (we will assume that the permutation N N-1 ... 3 2 1 is followed by the identical permutation, that is, 1 2 3 ... N).
Input
The first line of the input contains the number N (1 <= N <= 10000). The second line contains a permutation (a sequence of natural numbers from 1 to N separated by spaces).
Imprint
It is required to output the desired permutation.
Examples
| # |
Input |
Output |
| 1 |
3
1 3 2
| 2 1 3 |