Find the next permutation. Assume that the permutation (n, n - 1, \ldots, 2, 1) is followed by the identity permutation (1, 2, \ldots, n - 1, n).
The first line contains the number (1 \le n \le 10^5) — the number of elements in the permutation.
The second line contains a permutation of integers.
Print numbers — the next permutation for the given one.
Example 1