DMOPC '22 Contest 2 P3 - Good Permutations

View as PDF

Submit solution

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

Problem type

Mr. Gregory recently discovered the existence of \gcd. Enthralled by its beauty, he challenges you to a puzzle. Mr. Gregory gives you a target permutation T of the integers 1,2,\ldots,N. He tells you that a permutation P is good if it can be turned into T using the following operation any number of times: choose an integer i (1\leq i\leq N-1), such that \gcd(P_{i},P_{i+1})=1, and swap elements P_{i} and P_{i+1}. The answer to the puzzle is the lexicographically maximal good permutation P.

Prove your worth by solving the puzzle!


1 \le N \le 5 \times 10^5

1 \le T_i \le N

T is a permutation of the integers 1,2,\ldots,N

Subtask 1 [40%]

1 \le N \le 3 \times 10^3

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains the integer N.

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

Output Specification

Output N space-separated integers P_1,P_2,\ldots,P_N, the lexicographically maximal good permutation P.

Sample Input

2 1 3 4

Sample Output

3 2 4 1