The next permutation#2386

The next permutation

1 second
128 megabytes
Easy

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).

Input

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.

Output

Print numbers — the next permutation for the given one.

Examples

Example 1

Loading
Loading