You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

卡牌游戏

题目背景

大明和新新玩双人斗地主有点累了, 他们打算开发卡牌的新玩法.

题面翻译

有 $n$ 张卡牌，编号为 $1$, $2$, $...$, $n$。 最初，第 $i$ 张卡牌的分值为 $a_i$。 如果卡牌还大于等于 $1$ 就认为它还在桌面上, 否则出局。

我们可以重复以下的操作，直到只剩下一张卡牌为止：

• 任选两张卡牌 $A, B$, 让 $A$ 卡牌的分值变为 $A$ 减掉 $B$ 的分数.
• 如果某一张卡牌的分值 $\leq 0$, 这张卡牌应该出局.

求最后一张卡牌的分值最少是多少。

输入格式

第一行输入一个整数 $n$,

第二行 $n$ 个整数 $a_i$, 表示卡牌的分值。

输出格式

输出一个整数, 表示最后一张卡牌的分值最少是多少。

样例 #1

样例输入 #1

4
3 3 3 3

样例输出 #1

3

样例 #2

样例输入 #2

5
2 4 6 8 10

样例输出 #2

2

数据范围

• $2\ \leq\ n\ \leq\ 10^5$
• $1\ \leq\ a_i\ \leq\ 10^9$