Score : $300$ points

Problem Statement

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 \dots, N)$. Find the $(K-1)$-th lexicographically smallest permutation.

Constraints

• $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)$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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.

3
3 1 2

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)$.

10
9 8 6 5 10 3 1 2 4 7

9 8 6 5 10 2 7 4 3 1