题目描述

$(1,\ \dots,\ N)$ の順列 $P\ =\ (P_1,\ \dots,\ P_N)$ が与えられます。ただし、$(P_1,\ \dots,\ P_N)\ \neq\ (1,\ \dots,\ N)$ です。

$(1\ \dots,\ N)$ の順列を全て辞書順で小さい順に並べたとき、$P$ が $K$ 番目であるとします。辞書順で小さい方から $K-1$ 番目の順列を求めてください。

順列とは？ $(1,\ \dots,\ N)$ の順列とは、$(1,\ \dots,\ N)$ を並べ替えて得られる数列のことをいいます。

辞書順とは？ 長さ $N$ の数列 $ A\ =\ (A_1,\ \dots,\ A_N),\ B\ =\ (B_1,\ \dots,\ B_N) $ に対し、$A$ が $B$ より辞書順で真に小さいとは、ある整数 $1\ \leq\ i\ \leq\ N$ が存在して、下記の $2$ つがともに成り立つことをいいます。

• $(A_{1},\ldots,A_{i-1})\ =\ (B_1,\ldots,B_{i-1})$
• $A_i$

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P_1$ $\ldots$ $P_N$

输出格式

求める順列を $Q\ =\ (Q_1,\ \dots,\ Q_N)$ として、$Q_1,\ \dots,\ Q_N$ をこの順に空白区切りで一行に出力せよ。

题目大意

给出 1 到 $N$ 的一个排列（保证不是字典序最小的排列），求它按照字典序的上一个排列。

3
3 1 2

2 3 1

10
9 8 6 5 10 3 1 2 4 7

9 8 6 5 10 2 7 4 3 1

提示

制約

• $2\ \leq\ N\ \leq\ 100$
• $1\ \leq\ P_i\ \leq\ N\ \,\ (1\ \leq\ i\ \leq\ N)$
• $P_i\ \neq\ P_j\ \,\ (i\ \neq\ j)$
• $(P_1,\ \dots,\ P_N)\ \neq\ (1,\ \dots,\ N)$
• 入力される値は全て整数

Sample Explanation 1

$(1,\ 2,\ 3)$ の順列を辞書順で小さい順に並べると次のようになります。 - $(1,\ 2,\ 3)$ - $(1,\ 3,\ 2)$ - $(2,\ 1,\ 3)$ - $(2,\ 3,\ 1)$ - $(3,\ 1,\ 2)$ - $(3,\ 2,\ 1)$ よって $P\ =\ (3,\ 1,\ 2)$ は小さい方から $5$ 番目であり、求める順列、すなわち小さい方から $5\ -\ 1\ =\ 4$ 番目の順列は $(2,\ 3,\ 1)$ です。