分数: 300 点
问题陈述
给你一个排列 P = (P_1, \dots, P_N) of (1, \dots, N),其中 (P_1, \dots, P_N) \neq (1, \dots, N).
假设 P 是 K- 在所有排列中按字典顺序最小的 (1 \dots, N)。找到 (K-1)- 按字典顺序排列的最小排列。
什么是排列?
A 排列 of (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 满足以下两个条件。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
- A_i < B_i.
约束
- 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)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 \ldots P_N
输出
让 Q = (Q_1, \dots, Q_N) 是所寻求的排列。打印 Q_1, \dots, Q_N 按此顺序排列在一行中,以空格分隔。
示例输入 1
3 3 1 2
示例输出 1
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 - 1 = 4)是 (2, 3, 1).
示例输入 2
10 9 8 6 5 10 3 1 2 4 7
示例输出 2
9 8 6 5 10 2 7 4 3 1