题目描述

你有一张编号为 $1$ 到 $N$ 的 $N$ 张牌。每张卡片上都有一个整数，第 $i$ 张卡片上写有数字 $a_i$ 。

苏努里先生将完成以下程序。

1. $X$ 表示拥有的卡片上写着的最大值， $x$ 表示最小值。
2. 当 $X = x$ 时结束程序。否则，将所有写有 $X$ 的卡片转换为写有 $X - x$ 的卡片，然后执行第1步。

程序最终保证会结束。结束后，输出你持有的卡片上写着的唯一的数字。

输入格式

第一行输入一个整数 $N$ 。

接下来一行输入 $N$ 个整数 $a_i$ 。

输出格式

输出你持有的卡片上写着的唯一的数字。

样例 1

输入

3
2 6 6

输出

2

样例 2

输入

15
546 3192 1932 630 2100 4116 3906 3234 1302 1806 3528 3780 252 1008 588

输出

42

说明/提示

限制

$1 ≤ N ≤ 10^5$

$1 ≤ a_i ≤ 10^9$