Valentine's Day Gift Order Predecessor

It is Valentine's Day and Uim wants to prepare gifts for his harem. He has N girls (where \(1\le N\le 9\)). Uim has already determined the best order to give the gifts. However, he believes that things done too perfectly are not fun.

Thus, he desires to obtain the permutation that is immediately lexicographically previous to the given best order. If no such permutation exists, output -1.

A permutation is an ordering of the numbers from 1 to N. The lexicographical order is defined by comparing the values from left to right.

inputFormat

The first line contains an integer N, the number of girls.

The second line contains N space-separated distinct integers representing the current best gift order.

outputFormat

Output the lexicographically previous permutation as N space-separated integers. If the current order is the smallest permutation (i.e. no previous permutation exists), output -1.

sample

3
1 2 3

-1