配点 : $300$ 点

問題文

$N$ 体のモンスターが居て、それぞれ $1, 2, ..., N$ と番号付けられています。

はじめ、モンスター $i$ の体力は $A_i$ です。

以降、体力が $1$ 以上のモンスターを生きているモンスターと呼びます。

生きているモンスターが $1$ 体になるまで以下を繰り返します。

• ランダムに $1$ 体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。
• その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。

最後に生き残ったモンスターの最終的な体力の最小値を求めてください。

制約

• 入力は全て整数である。
• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$

入力

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

$N$

$A_1$ $A_2$ $...$ $A_N$

出力

最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。

4
2 10 8 40

2

$1$ 番目のモンスターだけが攻撃し続けた場合、最後に生き残ったモンスターの体力は $2$ となり、このときが最小です。

4
5 13 8 1000000000

1

3
1000000000 1000000000 1000000000

1000000000