← 返回题目列表

AtCoder · abc118_c

C. 怪物大逃杀

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 怪物,编号 1, 2, ..., N.

最初,怪物的生命值 i is A_i.

下面,至少有一个怪物 1 健康才叫活着。

直到只剩下一只活着的怪物为止,重复以下操作:

  • 一只随机活着的怪物攻击另一只随机活着的怪物。
  • 结果,被攻击的怪物的生命值减少了与攻击的怪物当前生命值相同的量。

找到最后一个活着的怪物的最小可能最终生命值。

约束

  • 输入中的所有值都是整数。
  • 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