P16978 [NWERC 2017] Factor-Free Tree

From [Northwestern Europe Regional Contest (NWERC) 2017](http://2017.nwerc.eu) Problem F. Original problem license: CC BY-SA.

A *factor-free tree* is a rooted binary tree where every node in the tree contains a positive integer value that is coprime with all of the values of its ancestors. Two positive integers are coprime if their greatest common divisor equals $1$. The *inorder sequence* of a rooted binary tree can be generated recursively by traversing first the left subtree, then the root, then the right subtree. See Figure 1 below for the inorder sequence of one factor-free tree. :::align{center}  ::: Figure 1: Illustration of Sample 1. The tree is factor-free; for example, the value of the node marked "$5$" is coprime with all of the values of its ancestors, marked "$9$", "$8$", and "$7$". Given a sequence $a_1,a_2,\ldots,a_n$, decide if it is the inorder sequence of some factor-free tree and if so construct such a tree.

The input consists of: - One line with one integer $n$ ($1 \leq n \leq 10^6$), the length of the sequence. - One line with $n$ integers $a_1,\ldots,a_n$ ($1 \leq a_i \leq 10^7$ for each $i$), the elements of the sequence.

If there exists a factor-free tree whose inorder sequence is the given sequence, output $n$ values. For each value in the sequence, give the $1$-based index of its parent, or $0$ if it is the root. If there are multiple valid answers, print any one of them. If no such tree exists, output `impossible` instead.