P16978 [NWERC 2017] 因子无关树 / Factor-Free Tree

译自 [Northwestern Europe Regional Contest (NWERC) 2017](http://2017.nwerc.eu) Problem F。 原题许可协议为 CC BY-SA。

一棵**因子无关树**是一棵有根二叉树，其中树上每个节点都包含一个正整数，并且这个正整数与它所有祖先节点中的数都互质。若两个正整数的最大公约数为 $1$，则称它们互质。 有根二叉树的**中序序列**可以递归生成：先遍历左子树，再遍历根节点，最后遍历右子树。下面的图 1 展示了一棵因子无关树的中序序列。 :::align{center}  ::: 图 1：样例 #1 的示意图。这棵树是因子无关的；例如，标为 $5$ 的节点的值与它所有祖先节点的值都互质，这些祖先节点标为 $9$、$8$ 和 $7$。 给定一个序列 $a_1,a_2,\ldots,a_n$，判断它是否是某棵因子无关树的中序序列；如果是，请构造出这样的一棵树。

输入包含： - 一行一个整数 $n$（$1 \leq n \leq 10^6$），表示序列长度。 - 一行 $n$ 个整数 $a_1,\ldots,a_n$（对于每个 $i$，$1 \leq a_i \leq 10^7$），表示该序列的元素。

如果存在一棵因子无关树，其 中序序列为给定序列，则输出 $n$ 个值。 对于序列中的每个值，输出它父亲节点的 $1$ 基下标；如果它是根节点，则输出 $0$。如果有多种合法答案，输出任意一种即可。 如果不存在这样的树，则输出 `impossible`。

对于所有数据，满足 $1 \leq n \leq 10^6$，$1 \leq a_i \leq 10^7$。若存在多种合法答案，输出任意一种即可。