eolymp
bolt
Try our new interface for solving problems
Problems

The next permutation

The next permutation

Time limit 1 second
Memory limit 128 MiB

Find the next permutation. Assume that permutation (n, n - 1, ..., 2, 1) is followed by the identity (1, 2, ..., n - 1, n).

Input data

First line contains the number n~(1 \le n \le 10^5) of elements in the permutation. Second line contains a permutation of n integers.

Output data

Print n numbers — the next permutation for the given one.

Examples

Input example #1
3
3 2 1
Output example #1
1 2 3