7388: ABC276 —— C - Previous Permutation
[Creator : ]
Description
You are given a permutation $P = (P_1, \dots, P_N)$ of $(1, \dots, N)$, where $(P_1, \dots, P_N) \neq (1, \dots, N)$.
Assume that P is the K-th lexicographically smallest among all permutations of (1…,N). Find the (K-1)-th lexicographically smallest permutation.
Assume that P is the K-th lexicographically smallest among all permutations of (1…,N). Find the (K-1)-th lexicographically smallest permutation.
Input
The input is given from Standard Input in the following format:
$N$
$P_1\ \ldots\ P_N$
$N$
$P_1\ \ldots\ P_N$
Output
Let $Q = (Q_1, \dots, Q_N)$ be the sought permutation. Print $Q_1, \dots, Q_N$ in a single line in this order, separated by spaces.
Constraints
$2≤N≤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)$
All values in the input are integers.
$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)$
All values in the input are integers.
Sample 1 Input
3
3 1 2
Sample 1 Output
2 3 1
Here are the permutations of (1, 2, 3) in ascending lexicographical order.
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).
Sample 2 Input
10
9 8 6 5 10 3 1 2 4 7
Sample 2 Output
9 8 6 5 10 2 7 4 3 1