Problem F
FactorFree Tree
A factorfree 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 factorfree tree.
Given a sequence $a_1, a_2, \ldots , a_ n$, decide if it is the inorder sequence of some factorfree tree and if so construct such a tree.
Input
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.
Output
If there exists a factorfree 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.
Sample Input 1  Sample Output 1 

6 2 7 15 8 9 5 
2 0 4 2 4 5 
Sample Input 2  Sample Output 2 

6 2 7 15 8 9 6 
impossible 