NPERM - Next Permuation

no tags 

Given a permutation P of the integers between 1 and n, find the smallest permutation Q sctrictly greater than P.

Permutations are compared lexicographically.

Input

In the first line there is an integer 1≤n≤105, the size of the permutation P.

In the next line, n different integers, 1 ≤ a≤ n, representing the permutation P.

Output

Single line with n integers, containing the permutation Q, or "NO" if the permutation does not exist.

Example

Input:
2
1 2

Output: 2 1

Input:
3
3 2 1

Output:

NO


Added by:Marcelo Fornet
Date:2018-01-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All