Next 3-1-2 pattern avoiding permutation

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.

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

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.