You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

A - 排列

题目描述

考虑到可能有人不知道排列是什么，这里解释一下：

• $1$ 到 $n$ 的排列是一个长度为 $n$ 序列，且包含数字 $1, 2, 3, \dots, n$ 各一次。

大明 有一个 $1$ 到 $n$ 的排列 $P = (P_1 , \dots, P_n)$ 。设 $P$ 的字典序是 $1$ 到 $n$ 的所有排列中第 $k$ 小的，请输出 $1$ 到 $n$ 的所有排列中，字典序第 $k - 1$ 小的排列。

输入格式

第一行 $1$ 个数 $n$ 。

第二行 $n$ 个数，表示 $P_1, P_2, \dots, P_n$ 。

输出格式

一行 $n$ 个数，表示字典序第 $k - 1$ 小的排列。

样例

输入 $1$

3
3 1 2

输出 $1$

2 3 1

样例解释 $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)$ 。

输入 $2$

8
6 7 5 4 1 2 3 8

输出 $2$

6 7 5 3 8 4 2 1

数据范围

对于所有数据，保证 $2 \le n \le 10^{5}$，$P$ 是 $1$ 到 $n$ 的排列，且 $(P_1, P_2,\dots ,P_n) \neq (1, 2, \dots,n)$ 。