Grammy 有一个长度为 $n$ 的数组。她最近学习了最大公约数（GCD）的概念。回想一下，数组的 GCD 是指能整除数组中每个元素的最大整数 $d$。Grammy 认为数组的 GCD 应该尽可能大，这样数组才会变得“优美”。

为了帮助 Grammy 让她的数组变得优美，你决定对数组中的每个元素进行若干次（可能为零次）取模运算。换句话说，你可以选择数组中的一个数 $a_i$ ($1 \le i \le n$)，再选择另一个整数 $x$，并将 $a_i$ 替换为 $(a_i \bmod x)$。由于 Grammy 不希望数组中出现 $0$，因此在进行取模运算时，你不能将 $a_i$ 变为 $0$。

现在，你的任务是计算在进行若干次（可能为零次）取模运算后，该数组可能达到的最大 GCD。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示数组中元素的个数。 第二行包含 $n$ 个正整数 $a_i$ ($1 \le a_i \le 10^9$)，表示 Grammy 数组的初始元素。

输出格式

输出一个整数，表示进行任意次取模运算后，数组的最大 GCD。

样例

样例输入 1

3
3 10 7

样例输出 1

3