Problem D
Factor-Free Tree

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.

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.

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 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.

6
2 7 15 8 9 5

2 0 4 2 4 5

6
2 7 15 8 9 6

impossible