A permutation of length $N$ is a sequence of distinct positive integers, each at most $N$. $ [1, 2, 3] $ and $ [3, 1, 2, 4] $ are valid permutations, while $ [6, 9] $ is not.

Given a permutation $P$ of length $N$, output the next plasticer permutation. The next plasticer permutation of $P$ refers to the lexicographically smallest permutation $Q$ that is lexicographically larger than $P$.

Permutation $P$ is lexicographically smaller than permutation $Q$ if and only if the following condition holds:

• In the first position where $P$ and $Q$ differ, $P$ has an element smaller than the corresponding element in $Q$.

Input

The first line of the input contains an integer $N (1 \le N \le 10^6)$, the length of $P$.
The second line of the input contains $N$ integers $P_1, P_2, \dots ,P_N,$ the elements of the permutation $P$.

Output

If next plasticer permutation $Q$ exists, output $N$ integers $Q_1, Q_2, \dots ,Q_N$ separated by a space.
Otherwise, output So plastic already.

Hint

useful function

useful example

google search