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
.
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
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
Comments
Why do I keep getting WA for my submission? I have no clue what I did wrong: https://dmoj.ca/src/5071271