Divisor

Time Limit : 1 sec, Memory Limit : 65536 KB

問題文

正整数列 $X_1,X_2,...,X_N$ がある。数列 $\{1,2,...,N\}$ から部分列 $S$ を選ぶ。ただし $S$ は以下の条件を満たす必要がある。

  • $T=\{X_s | s \in S\}$ とする。このとき、任意の $x \in T$ について、$x$ の約数(ただし $x$ は除く)は $T$ に含まれない。

条件を満たす $S$ のうち、最も多くの要素を含むものを求めよ。また、そのような $S$ が複数ある場合は辞書式順序で最小のものを求めよ。

入力

入力は以下の形式に従う。与えられる数は全て整数である。

$N$
$X_1$ $X_2$ $...$ $X_N$

制約

  • $1 \leq N \leq 100$
  • $1 \leq X_i \leq 10^8$
  • $i \neq j$ ならば $X_i \neq X_j$

出力

求める $S$ の各要素を1行にスペースを空けて昇順で出力せよ。

Sample Input 1

3
25 125 5

Output for the Sample Input 1

1

$T=\{X_1\}=\{25\}$ は条件を満たす。

Sample Input 2

3
6 3 2

Output for the Sample Input 2

2 3

$T=\{X_2,X_3\}=\{2,3\}$ は条件を満たす。

Sample Input 3

10
10 9 8 7 6 5 4 3 2 1

Output for the Sample Input 3

1 2 3 4 5

$T=\{X_1,X_2,X_3,X_4,X_5\}=\{6,7,8,9,10\}$ は条件を満たす。 $T=\{X_1,X_2,X_4,X_5,X_7\}=\{4,6,7,9,10\}$ も条件を満たすが、$\{1,2,4,5,7\}$は $\{1,2,3,4,5\}$ より辞書順で大きいので答とはならない。


Source: Osaka University Programming Contest 2012 , Osaka, Japan, 2012-03-18