Factor-Free Tree

A factor-free tree is a rooted binary tree in which every node holds one positive integer, and the value of every node is coprime with the values of all of its ancestors. Two positive integers are coprime when their greatest common divisor is 1.

The inorder sequence of a rooted binary tree is built recursively: first the left subtree, then the root, then the right subtree.

The tree above is factor-free. For example, the value 5 is coprime with the values 9, 8 and 7 written in the ancestors of that node.

You are given a sequence $a_1, a_2, \dots, a_n$. Decide whether some factor-free tree has this sequence as its inorder sequence, and build such a tree if one exists.

The first line contains the length of the sequence $n$ ($1 \le n \le 10^6$).

The second line contains the integers $a_1, \dots, a_n$ of the sequence, separated by spaces ($1 \le a_i \le 10^7$).

If a factor-free tree has the given sequence as its inorder sequence, print $n$ numbers on one line, separated by spaces. The $i$-th number is the 1-based index of the parent of the $i$-th element, or 0 if the $i$-th element is the root.

Several trees can satisfy the condition, so only the tree built by the following rule counts as correct. Build the tree of a block of consecutive positions $[l, r]$ like this. Take as its root the smallest position $m$ in the block whose value is coprime with every other value of the block, then build the left subtree by applying the same rule to the block $[l, m-1]$ and the right subtree by applying it to the block $[m+1, r]$. The whole sequence is the block $[1, n]$. If some block has no such position, no factor-free tree has the given sequence as its inorder sequence.

If no such tree exists, print impossible instead.