Previous Permutation

You are given one permutation of the numbers $1$ through $N$. Write a program that finds the permutation that comes immediately before it in lexicographic order.

The first permutation in lexicographic order is the one sorted in ascending order, and the last one is the permutation sorted in descending order.

For $N = 3$, the permutations listed in lexicographic order are:

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

The first line contains $N$ ($1 \le N \le 10000$). The second line contains a permutation of the numbers $1$ through $N$, separated by spaces.

On the first line, print the permutation that comes immediately before the given one, separated by spaces. If the given permutation is the first one in lexicographic order, print $-1$.