# The next permutation

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤n≤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

Input #1

Answer #1

Submissions 2K

Acceptance rate 37%