Max Subset GCD

問題文

長さ $N$ の数列 $A = (A_1, A_2, ...\, , A_N)$ が与えられます。 また、数列 $A$ の空でない部分列を $T$ とします。

ここで、$T$ に対するスコア $f(T)$ を以下のように定義します。

• $T$ の長さが $m$ であるとき、$f(T) = \gcd(T_1, T_2, ...\, , T_m) \times m$

考えられる $T$ は $2^N-1$ 通りありますが、そのうち $f(T)$ の最大値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^5$
• 入力は全て整数

入力

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

出力

$f(T)$ の最大値を出力せよ。

サンプル

サンプル1

3
4 6 3

6

• $T = (4)$ のとき，$f(T) = \gcd(4) \times 1 = 4$
• $T = (6)$ のとき，$f(T) = \gcd(6) \times 1 = 6$
• $T = (3)$ のとき，$f(T) = \gcd(3) \times 1 = 3$
• $T = (4,6)$ のとき，$f(T) = \gcd(4,6) \times 2 = 4$
• $T = (4,3)$ のとき，$f(T) = \gcd(4,3) \times 2 = 2$
• $T = (6,3)$ のとき，$f(T) = \gcd(6,3) \times 2 = 6$
• $T = (4,6,3)$ のとき，$f(T) = \gcd(4,6,3) \times 3 = 3$

以上より，$6$ が正解です．

サンプル2

7
12 6 4 7 8 6 16

18