题目描述

徐老师的小本子上有 $n$ 个数字依次为 $a_1,a_2,a_3 \dots a_n$

而徐老师觉得数字太多了没什么意思，于是他有了一个想法——用模运算来合并这个序列

徐老师每次会任选序列中的两个数字 $a_i,a_j(i!=j)$ 进行合并，合并的结果是 $a_i \% a_j$

可以简单理解为，徐老师每次会选出两个数字 $a_i$ 和 $a_j$ 删除，再将 $a_i \% a_j$ 写到小本子上

总共进行 $n - 1$ 次合并，最后小本子上会只剩下一个数字，现在徐老师想知道这个数字最大可以是多少？

输入格式

输入第一行是一个整数 $n$，表示徐老师小本子上的数字个数

输入第二行是 $n$ 个整数，用空格隔开，分别表示每个数字

输出格式

输出一行，包含一个整数，表示最后剩下的最大数字可能是多少

数据范围

对于 $20\%$ 的数据，保证 $1 \leq n \leq 2$；

对于 $40\%$ 的数据，保证 $1 \leq n \leq 3$；

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^{5}$。

对于所有数据保证：$1 \leq a_i \leq 10^6$，且所有 $a_i$ 均不相同

样例输入

3
3 5 1

样例输出

1

样例解释

1. 选择 $a_2$ 和 $a_1$ 合并得到 $5 \% 3 = 2$，序列变为 $[1,2]$
2. 选择 $a_1$ 和 $a_2$ 合并得到 $1 \% 2 = 1$，序列变为 $[1]$

没有方案可以生成比 $1$ 更大的数字