AT_abc118_c [ABC118C] Monsters Battle Royale

题目描述

有 $N$ 只怪兽，编号为 $1, 2, \ldots, N$。

一开始，第 $i$ 只怪兽的体力为 $A_i$。

接下来，体力大于等于 $1$ 的怪兽被称为“活着的怪兽”。

重复以下操作，直到只剩下一只活着的怪兽为止：

• 随机选择一只活着的怪兽，随机攻击另一只活着的怪兽。
• 被攻击的怪兽体力减少等于攻击者体力的数值。

请你求出最后剩下的那只怪兽最终体力的最小值。

输入格式

输入以如下格式从标准输入中给出。

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

输出格式

输出最后剩下的那只怪兽最终体力的最小值。

样例 1

输入

4
2 10 8 40

输出

2

样例 2

输入

4
5 13 8 1000000000

输出

1

样例 3

输入

3
1000000000 1000000000 1000000000

输出

1000000000

说明/提示

限制条件

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

样例解释 1

如果只有第 $1$ 只怪兽一直进行攻击，最后剩下的怪兽体力为 $2$，这是最小值。

由 ChatGPT 4.1 翻译