Background

From Northwestern Europe Regional Contest (NWERC) 2017 Problem F.

Original problem license: CC BY-SA.

Problem Description

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.

Input Format

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 Format

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