C - Monsters Battle Royale 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

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

入力例 1

4
2 10 8 40

出力例 1

2

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

入力例 2

4
5 13 8 1000000000

出力例 2

1

入力例 3

3
1000000000 1000000000 1000000000

出力例 3

1000000000

Score : 300 points

Problem Statement

There are N monsters, numbered 1, 2, ..., N.

Initially, the health of Monster i is A_i.

Below, a monster with at least 1 health is called alive.

Until there is only one alive monster, the following is repeated:

  • A random alive monster attacks another random alive monster.
  • As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.

Find the minimum possible final health of the last monster alive.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible final health of the last monster alive.

Sample Input 1

4
2 10 8 40

Sample Output 1

2

When only the first monster keeps on attacking, the final health of the last monster will be 2, which is minimum.

Sample Input 2

4
5 13 8 1000000000

Sample Output 2

1

Sample Input 3

3
1000000000 1000000000 1000000000

Sample Output 3

1000000000