P1031 - Previous Permutation

Memory Limit：1024 MB Time Limit：2.000 S

Judge Style：Text Compare Creator：

Submit：15 Solved：10

Submit Submit Record Statistics ShowOff!

You are given a permutation $lns="http://www.w3.org/1998/Math/MathML"> � = (�_{1}, \dots, �_{�})$ of $lns="http://www.w3.org/1998/Math/MathML"> (1, \dots, �)$ , where $lns="http://www.w3.org/1998/Math/MathML"> (�_{1}, \dots, �_{�}) \neq (1, \dots, �)$ .

Assume that $lns="http://www.w3.org/1998/Math/MathML"> �$ is the $lns="http://www.w3.org/1998/Math/MathML"> �$ -th lexicographically smallest among all permutations of $lns="http://www.w3.org/1998/Math/MathML"> (1 \dots, �)$ . Find the $lns="http://www.w3.org/1998/Math/MathML"> (� - 1)$ -th lexicographically smallest permutation.

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

$N$

 $P_{1}$   $lns="http://www.w3.org/1998/Math/MathML"> \dots$   $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$

$2 \leq N \leq 100$
$lns="http://www.w3.org/1998/Math/MathML"> 1 \leq �_{�} \leq � (1 \leq � \leq �)$
$lns="http://www.w3.org/1998/Math/MathML"> �_{�} \neq �_{�} (� \neq �)$
$lns="http://www.w3.org/1998/Math/MathML"> (�_{1}, \dots, �_{�}) \neq (1, \dots, �)$
All values in the input are integers.

Let $lns="http://www.w3.org/1998/Math/MathML"> � = (�_{1}, \dots, �_{�})$ be the sought permutation. Print $lns="http://www.w3.org/1998/Math/MathML"> �_{1}, \dots, �_{�}$ in a single line in this order, separated by spaces.

3
3 1 2

2 3 1

Here are the permutations of $lns="http://www.w3.org/1998/Math/MathML"> (1, 2, 3)$ in ascending lexicographical order.

$lns="http://www.w3.org/1998/Math/MathML"> (1, 2, 3)$
$lns="http://www.w3.org/1998/Math/MathML"> (1, 3, 2)$
$lns="http://www.w3.org/1998/Math/MathML"> (2, 1, 3)$
$lns="http://www.w3.org/1998/Math/MathML"> (2, 3, 1)$
$lns="http://www.w3.org/1998/Math/MathML"> (3, 1, 2)$
$lns="http://www.w3.org/1998/Math/MathML"> (3, 2, 1)$

Therefore, $lns="http://www.w3.org/1998/Math/MathML"> � = (3, 1, 2)$ is the fifth smallest, so the sought permutation, which is the fourth smallest $lns="http://www.w3.org/1998/Math/MathML"> (5 - 1 = 4)$ , is $lns="http://www.w3.org/1998/Math/MathML"> (2, 3, 1)$ .

Atcoder

Submit Submit Record Statistics ShowOff!

1031: Previous Permutation

Description

Input

Output

Sample Input Copy

Sample Output Copy

HINT

Source/Category