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