Monsters Battle Royale

题目描述

有 $N$ 个怪物，编号为 $1, 2, ..., N$。 最初，怪物 $i$ 的生命值为 $A_i$。 下面，生命值至少为 $1$ 的怪物称为存活。 直到只剩下一个存活的怪物为止，重复以下过程：

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

求最后存活的唯一怪物的最小可能生命值。

输入格式

输入按以下格式从标准输入给出： $N$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出最后存活的唯一怪物的最小可能生命值。

4
2 10 8 40

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$当只有第一个怪物持续进行攻击时，最后存活的怪物生命值为 $2$，这是最小值。

标签: AtCoder|abc118C

来源

AtCoder|abc118C