题目描述

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.

有 $N$ 只怪物，编号为 $1, 2, ..., N$ 。

最初，怪物 $i$ 的健康值是 $A_i$ 。

下面，健康值至少为 $1$ 的怪物被称为 "活着"。

直到只有一个活着的怪物为止，重复以下步骤：

• 一个随机的活着的怪物攻击另一个随机的活着的怪物。
• 结果，被攻击怪物的生命值会减少，减少的数量等于攻击怪物当前的生命值。

找出最后一个活着的怪物的最小最终健康值。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印最后一只活着的怪物的最小最终健康值。

样例 #1

样例输入 #1

4
2 10 8 40

样例输出 #1

2

样例 #2

样例输入 #2

4
5 13 8 1000000000

样例输出 #2

1

样例 #3

样例输入 #3

3
1000000000 1000000000 1000000000

样例输出 #3

1000000000

说明

数据规模与约定

• 所有输入值均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$

样例 $1$ 解释

当只有第一只怪物持续攻击时，最后一只怪物的最终健康值为 $2$ ，即最小值。