题目描述

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

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

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

有 $N$ 只怪兽，编号为 $1$, $2$, $...$, $N$。 最初，第 $i$ 只怪兽的生命值为 $A_i$。 如果怪兽的生命值还大于等于 $1$ 就认为它是存活的。

怪兽们会重复以下的操作，直到只剩下一只存活的怪兽为止：

• 某一只存活的怪兽攻击会另外一只存活的怪兽。
• 被攻击的怪兽的生命值会减去发动攻击的怪兽生命值。

求最后一个存活的怪兽剩余生命值最少是多少。

4
2 10 8 40

2

4
5 13 8 1000000000

1

3
1000000000 1000000000 1000000000

1000000000

提示

制約

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

Sample Explanation 1

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