서로소 트리

서로소 트리는 뿌리 있는 이진 트리 가운데, 모든 노드에 양의 정수가 하나씩 적혀 있고 각 노드의 값이 그 노드의 모든 조상 노드의 값과 서로소인 트리다. 두 양의 정수는 최대공약수가 1일 때 서로소다.

뿌리 있는 이진 트리의 중위 순회 수열은 왼쪽 서브트리, 뿌리, 오른쪽 서브트리 순서로 재귀적으로 만든다.

위 그림의 트리는 서로소 트리다. 예를 들어 5가 적힌 노드의 값은 조상 노드에 적힌 9, 8, 7과 모두 서로소다.

수열 $a_1, a_2, \dots, a_n$이 주어진다. 이 수열을 중위 순회 수열로 갖는 서로소 트리가 있는지 판단하고, 있으면 그런 트리를 하나 만든다.

첫째 줄에 수열의 길이 $n$이 주어진다. ($1 \le n \le 10^6$)

둘째 줄에 수열을 이루는 정수 $a_1, \dots, a_n$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^7$)

주어진 수열을 중위 순회 수열로 갖는 서로소 트리가 있으면 $n$개의 수를 한 줄에 공백으로 구분해 출력한다. $i$번째 수는 $i$번째 원소의 부모가 수열에서 몇 번째 원소인지를 나타내고, $i$번째 원소가 뿌리면 0이다.

조건을 만족하는 트리가 여러 개일 수 있으므로, 다음 규칙으로 만든 트리만 정답으로 인정한다. 연속한 구간 $[l, r]$에 해당하는 트리는 이렇게 만든다. 구간 안의 나머지 모든 값과 서로소인 위치 가운데 번호가 가장 작은 위치 $m$을 뿌리로 삼고, 왼쪽 서브트리는 구간 $[l, m-1]$에, 오른쪽 서브트리는 구간 $[m+1, r]$에 같은 규칙을 다시 적용해서 만든다. 전체 수열은 구간 $[1, n]$이다. 이 과정에서 어떤 구간에 그런 위치가 하나도 없으면, 주어진 수열을 중위 순회 수열로 갖는 서로소 트리는 존재하지 않는다.

그런 트리가 없으면 impossible을 출력한다.