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≤10⁵, the size of the permutation P.

In the next line, n different integers, 1 ≤ a_i ≤ 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