Previous Permutation

题目描述

你被给定了一个排列 $P = (P_1, \dots, P_N)$，它是 $(1, \dots, N)$ 的一个排列，且 $(P_1, \dots, P_N) \neq (1, \dots, N)$。 假设 $P$ 是所有 $(1 \dots, N)$ 的排列中按字典序第 $K$ 小的。求按字典序第 $(K-1)$ 小的排列。

输入格式

输入从标准输入给出，格式如下： $N$ $P_1$ $\ldots$ $P_N$

输出格式

设 $Q = (Q_1, \dots, Q_N)$ 为所求的排列。按顺序以空格分隔输出 $Q_1, \dots, Q_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)$ 输入中的所有数值均为整数。下面是 $(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 小，所以所求的排列，即第 4 小 $(5 - 1 = 4)$，是 $(2, 3, 1)$。

标签: AtCoder|abc276C

来源

AtCoder|abc276C