怪物战斗

题目描述

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

一开始,怪物 $i$ 的体力为 $A_i$。

此后,体力在 $1$ 以上的怪物称为活着的怪物。

重复以下操作,直到活着的怪物只剩 $1$ 只:

• 随机选 $1$ 只活着的怪物,随机攻击另一只活着的怪物。
• 其结果是,被攻击的怪物的体力减少攻击怪物体力值那么多。

求最后幸存下来的怪物最终体力的最小值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出最后幸存下来的怪物最终体力的最小值。

样例

4
2 10 8 40

2

如果只有第 $1$ 只怪物持续攻击,最后幸存怪物的体力为 $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$