← 返回题目列表

AtCoder · abc276_c

E. 先前的排列

中文机器翻译题面 查看原题

分数: 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