「EZEC-9」GCD Tree
题目背景
规定 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数，$\operatorname{lca}(x,y)$ 表示 $x$ 号节点和 $y$ 号节点的最近公共祖先。
题目描述
给你 $n$ 个点，编号分别为 $1,2,\ldots,n$，点权分别为 $a_1,a_2,\ldots,a_n$。
请你用这 $n$ 个点构造一棵树，使得 $\forall 1 \le i < j \le n$，$\gcd(a_i, a_j) = a_{\operatorname{lca}(i, j)}$。
若无解，报告之，否则输出树的形态。
输入输出格式
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1, a_2, \ldots , a_n$。
输出格式
若无解，输出 `-1`;
否则输出一行 $n$ 个整数，第 $i$ 个数表示 $i$ 号节点的父节点编号。特别地，若 $i$ 号节点为根节点则输出 `0`。
若有多解，输出任意一解即可。
输入输出样例
输入样例 #1
5
1 2 3 4 5
输出样例 #1
0 1 1 2 1
输入样例 #2
5
1 2 3 4 6
输出样例 #2
-1
说明
**【数据规模与约定】**
**本题采用捆绑测试。**
- Subtask 1（5 points）：$n = 2$。
- Subtask 2（5 points）：所有 $a_i$ 均相等。
- Subtask 3（5 points）：$n \le 5$。
- Subtask 4（10 points）：保证有解。
- Subtask 5（15 points）：$n \le 100$。
- Subtask 6（15 points）：$n \le 10^3$。
- Subtask 7（15 points）：$n \le 3 \times 10^3$。
- Subtask 8（30 points）：无特殊限制。
对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le a_i \le 10^6$。