Previous Permutation

Interview

Time limit1sMemory limit256 MB

Summary

Given a permutation of 1 to N, print the permutation that comes just before it in lexicographic order, or -1 when it is the first.

Level: Medium4 of 10
Topics: Array
Solved: No attempts yet

Problem

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

Input

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.

Output

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$ .

Examples5

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
-1
```
Example 2
Input
```
5
5 4 3 2 1
```
Expected output
```
5 4 3 1 2
```
Example 3
Input
```
1
1
```
Expected output
```
-1
```
Example 4
Input
```
2
2 1
```
Expected output
```
1 2
```
Example 5
Input
```
3
2 1 3
```
Expected output
```
1 3 2
```