The next permutation

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

Input

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

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

Examples