前一个排列

题目描述

给你一个 $(1, \dots, N)$ 的排列 $P = (P_1, \dots, P_N)$,其中 $(P_1, \dots, P_N) \neq (1, \dots, N)$。

假设 $P$ 是 $(1 \dots, N)$ 的所有排列中字典序第 $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 \lt B_i$

输入格式

输入按以下格式从标准输入给出:

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

输出格式

设所求排列为 $Q = (Q_1, \dots, Q_N)$。在一行内按此顺序用空格分隔输出 $Q_1, \dots, Q_N$。

样例

3
3 1 2

2 3 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)$。

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)$
• 输入中的所有值均为整数。