题目描述

给定一个排列 $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 < 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