Next permutation

Interview

Time limit1sMemory limit256 MB

Summary

Given a permutation of 1 to N, print the next permutation in lexicographic order, or -1 when the given one is the last.

Level: Medium4 of 10
Topics: Array, Two pointers
Solved: No attempts yet

Problem

You are given one permutation of the numbers from 1 to $N$ . Write a program that finds the permutation that comes right after it in lexicographic order.

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

For $N = 3$ , the permutations 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 from 1 to $N$ , separated by spaces.

Output

On the first line, print the permutation that comes right after the given one in lexicographic order, separated by spaces. If the given permutation is the last one in lexicographic order, print -1.

Examples6

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