AT_agc010_e [AGC010E] Rearranging
Description
[problemUrl]: https://atcoder.jp/contests/agc010/tasks/agc010_e
黒板に $ N $ 個の整数が書かれています。$ i $ 番目の整数は $ A_i $ です。
高橋君と青木君は以下の手順でこれらの数を一列に並べることにしました。
- 最初に、高橋君が好きな順に一列に並べる。
- 次に、青木君が隣り合う $ 2 $ つの数を選んで入れ替えることを好きな回数だけ繰り返す。
ただし、入れ替える $ 2 $ 数は互いに素でなければならない。
高橋君は最終的な並びが辞書順最小となるように、青木君は最終的な並びが辞書順最大となるように最適に行動するとしたとき、 最終的な数列を求めてください。
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 1\ ≦\ N\ ≦\ 2000 $
- $ 1\ ≦\ A_i\ ≦\ 10^8 $
### Sample Explanation 1
高橋君は与えられた数を $ (1,2,3,4,5) $ という順番で並べれば、青木君が最適に動かしても $ (5,3,2,4,1) $ となります。