AT_abc276_c [ABC276C] Previous Permutation

[problemUrl]: https://atcoder.jp/contests/abc276/tasks/abc276_c $ (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 $ をこの順に空白区切りで一行に出力せよ。

### 制約 - $ 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) $ です。