背景

译自 Northwestern Europe Regional Contest (NWERC) 2017 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。

6
2 7 15 8 9 5

2 0 4 2 4 5

6
2 7 15 8 9 6

impossible

提示

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