题目描述

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

一开始，怪物$i$的生命值为 $A_i$;。下面，生命值至少为 1的怪物称为存活直到只剩下一只存活的怪物重复以下操作:

一只随机存活的怪物攻击另一只随机存活的怪物。

作为结果，被攻击怪物的生命值减少的量等于攻击怪物的当前生命值。

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

输入

第一行一个整数$N$表示怪物的数量

第二行$N$个数表示每个怪物的生命值

输出

最后一只存活的怪物的最小可能的最终生命值。

4
2 10 8 40

2

样例解释

当只有第一只怪物持续攻击时，最后一只怪物的最终生命值为 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$