## DMOPC '22 Contest 2 P3 - Good Permutations

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Mr. Gregory recently discovered the existence of . Enthralled by its beauty, he challenges you to a puzzle. Mr. Gregory gives you a target permutation of the integers . He tells you that a permutation is good if it can be turned into using the following operation any number of times: choose an integer , such that , and swap elements and . The answer to the puzzle is the lexicographically maximal good permutation .

Prove your worth by solving the puzzle!

#### Constraints

is a permutation of the integers

#### Input Specification

The first line contains the integer .

The next line contains space-separated integers, representing the target permutation .

#### Output Specification

Output space-separated integers , the lexicographically maximal good permutation .

#### Sample Input

4
2 1 3 4

#### Sample Output

3 2 4 1