当一棵二叉树中的每个节点的权值都与它所有祖先的权值互质时，我们称它为 factor-free tree。
给你一棵按照中序遍历的顺序的权值序列 \(a\)，求这个序列是否对应这一棵 factor-free tree。
如果是就输出每个节点的父亲。
\(n \le 10^5, a_i \le 10^7\)。
考虑怎么找到一棵 factor-free tree：先找到一个与其他所有数都互质的数当根，然后再递归左右两边。可以注意到如果有多个数互质选哪个都是无所谓的，因为最后总会将序列划分成相同的形态。
为了做这个东西，首先要能快速判断一个数是否与这个区间内的其他数互质。这个可以考虑对每个位置预处理出 \(L_i\) 和 \(R_i\) 表示这个数左右两边第一个不和它互质的数，然后对于一个区间 \([l, r]\)，判断区间内的数手否和它互质就是判断是否有 \(L_i \le l, r \le R_i\)。
然后可以发现这个东西最慢是 \(O(n^2)\) 的，所以还要继续优化。
对于这个递归过程，想要让它的时间复杂度正确，需要要求每次遍历的时间复杂度和 \([l, mid]\) 和 \([mid, r]\) 中较短的区间的长度相关，这样就是 \(O(n \log n)\) 的。所以考虑怎么让每次遍历的时间复杂度变成 \(O(\min(mid - l, r - mid))\)。
我们可以从 \(l\) 和从 \(r\) 同时找，这样就是 \(O(\min(mid - l, r - mid))\) 的了。
时间复杂度 \(O(n \log n)\)。
constexpr int MAXN = 1e6 + 9, MAXV = 1e7 + 9, MAXP = 7e5;
int n, a[MAXN], mnp[MAXV], id[MAXV], L[MAXN], R[MAXN],
fa[MAXN];
vector<int> pri, pos[MAXP];
bitset<MAXV> vis;
void sieve(int N) {
vis.reset();
for (int i = 2; i <= N; i ++) {
if (!vis[i]) {
id[i] = pri.size();
pri.emplace_back(i);
mnp[i] = i;
}
for (auto j : pri) {
if (1ll * i * j > N) break;
vis[i * j] = 1, mnp[i * j] = j;
if (i % j == 0) break;
}
}
return;
}
bool Solve(int l, int r, int rt) {
if (l > r) return true;
int pl = l, pr = r, mid = 0;
auto check = [&](int x) { return L[x] <= l && r <= R[x]; };
while (pl <= pr) {
if (check(pl)) { mid = pl; break; }
if (check(pr)) { mid = pr; break; }
pl ++, pr --;
}
if (mid) { fa[mid] = rt; return Solve(l, mid - 1, mid) && Solve(mid + 1, r, mid); }
return false;
}
void slv() {
n = Read<int>(), sieve(1e7);
for (int i = 1; i <= n; i ++) a[i] = Read<int>();
auto Divide = [&](int p) {
int t = a[p];
while (t != 1) {
pos[id[mnp[t]]].emplace_back(p);
t /= mnp[t];
}
return;
};
for (int i = 1; i <= n; i ++) Divide(i), L[i] = 0, R[i] = n + 1;
for (int i = 0; i < pri.size(); i ++) {
pos[i].emplace_back(0), pos[i].emplace_back(n + 1);
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
for (int j = 1; j + 1 < pos[i].size(); j ++)
cmax(L[pos[i][j]], pos[i][j - 1] + 1),
cmin(R[pos[i][j]], pos[i][j + 1] - 1);
}
if (!Solve(1, n, 0)) { Puts("impossible"); return; }
for (int i = 1; i <= n; i ++) Write(fa[i], ' ');
return;
}