题目描述

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

初始时，第 $i$ 只怪物的生命值是 $A_i$。

在接下来的过程中，重复以下步骤直到只剩下一只活着的怪物：

• 选取一只随机的活着的怪物，攻击另一只随机的活着的怪物。
• 攻击后，被攻击的怪物的生命值减少与攻击者当前生命值相等的数值。

找出最后一只活着的怪物的可能的最小生命值。

约束条件

• 输入中的所有值均为整数。
• $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

当只有第一只怪物不停地攻击时，最后一只怪物的生命值是 $2$，这是可能的最小值。

示例输入 2

4
5 13 8 1000000000

示例输出 2

1

示例输入 3

3
1000000000 1000000000 1000000000

示例输出 3

1000000000