看错题了，我一开始没看到要求最小化那个不同种类数，但我也做出来了。
我想的就是研究这个性质，首先设原序列是 $a$，gcd 序列是 $b$，然后你发现我们一定要求 $lcm(b_i,b_{i+1})=a_{i+1}$。
然后呢你找 $b$，然后你发现如果 $p|b_{i-1},p|b_{i+1}$ 于是 $p|b_i$，$(b_{i-1},b_{i+1})|b_i$。
然后你发现这个是充要条件，然后一个构造就是 1 n/2, 2, n / 2 + 1…..。
然而这样没有限制最小化不同种类数，但无论如何这个性质还是蛮厉害的。
然后回到正题，你发现你看错题了。
然后我们想着这个既然要最小是吧，那我们就直接想一下最小是多少，显然是不能小于 $k$ 满足 $k$ 个点的图的欧拉路径长度等于 $n$。
然后你试图构造发现你不会构造。
你乱搞一波，然后发现 easy version 可以 $2^i3^{m-i}$。
然后你发现你如法炮制，$2^{i}3^{m-i}5^{j}7^{k-j}$。
然而你发现你这个对应交换 $i,j$ 也会被判为相同。
然后你发现你还剩了蛮多位置。然后变成 $2^{i+j}3^{i}5^{m-i}7^{j}11^{k-j}$ 即可。
注意欧拉路径写法，不要像我一样 wa 十几发。