006 - コプライムソート

あなたは、与えられた数列を昇順に並べ替えるために、一風変わった方法を考察している。その方法では、与えられた数列に対して、共通の素因数を持つ要素同士の位置のみ交換できる。たとえば数列「6 4 2 3 7」が与えられたとき、以下のようにすれば整列可能である。

Step 0 : 6 4 2 3 7 (与えられた数列)
Step 1 : 2 4 6 3 7 (要素 6 と 2 を交換)
Step 2 : 2 6 4 3 7 (要素 4 と 6 を交換)
Step 3 : 2 3 4 6 7 (要素 6 と 3 を交換)

ただし、与えられた数列によっては、整列させることができない場合がある。あなたはこの方法を、コプライムソートと名付け、与えられた数列がコプライムソートで整列させることができるか調べることにした。

与えられた整数の数列に対して、共通の素因数を持つ要素同士を交換する操作を任意の回数行うことで、その数列を昇順に整列できるかを判定するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$a_1$ $a_2$ $...$ $a_N$

１行目に数列の要素数$N$ ($2 \leq N \leq 10^5$)が与えられる。続く１行に、数列の各要素を表す整数$a_i$ ($2 \leq a_i \leq 10^5$)が与えられる。

出力

昇順に整列することができる場合は「1」、できない場合は「0」を出力する。

入出力例

入力例１

5
6 4 2 3 7

出力例１

1

入力例２

7
2 9 6 5 6 7 3

出力例２

0