Next 3-1-2 pattern avoiding permutation

Time limit0.1sMemory limit32 MB

Summary

Given a 3-1-2-avoiding permutation of 1 to n, print the next one in lexicographic order.

Level: Hard8 of 10
Topics: Combinatorics, Greedy, Implementation
Solved: No attempts yet

Problem

Pattern avoidance in permutations is a long studied topic in combinatorics and computer science. A permutation $p_1, p_2, \dots, p_n$ of the natural numbers $1, \dots, n$ avoids the 3-1-2 pattern if there are no indices $1 \le i < j < k \le n$ with $p_i > p_j$ , $p_i > p_k$ and $p_j < p_k$ .

List every permutation of $1, \dots, n$ that avoids the 3-1-2 pattern in lexicographic order. Given one permutation from that list, compute the permutation that follows it. The decreasing sequence $n, n-1, \dots, 1$ is the last entry of the list, and the input is never that permutation, so the answer always exists.

Input

The first line contains an integer $n$ ( $3 \le n \le 10000$ ). The second line contains a permutation of $1, \dots, n$ as $n$ integers separated by single spaces. The permutation avoids the 3-1-2 pattern and is not the decreasing sequence $n, n-1, \dots, 1$ .

Output

Print on the first line the permutation that follows the input permutation in the lexicographic order of all 3-1-2 pattern avoiding permutations. Separate the numbers with single spaces.

Examples3

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