AT_abc276_c.[ABC276C] Previous Permutation

给定一个 $ (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) $，若存在某个整数 $ 1 \leq i \leq N $，同时满足以下两个条件，则称 $ A $ 字典序严格小于 $ B $：

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

输入从标准输入中给出，格式如下：

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

请输出所求的排列 $ Q = (Q_1,\ \dots,\ Q_N) $，用空格分隔，输出一行。

限制条件

• $ 2 \leq N \leq 100 $
• $ 1 \leq P_i \leq N \quad (1 \leq i \leq N) $
• $ P_i \neq P_j \quad (i \neq j) $
• $ (P_1,\ \dots,\ P_N) \neq (1,\ \dots,\ N) $
• 输入的所有值均为整数

样例解释 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) $。

由 ChatGPT 4.1 翻译