暂无测试数据。

最大公约数 $gcd(a,b)$ 是指正整数 $a,b$ 的公共约数中最大的那个数

定义次大公约数函数 $f(a,b)$，当 $gcd(a,b)=1$ 时 $f(a,b)=0$，否则 $f(a,b)$ 为 $a,b$ 的公约数中第二大的那个数

比如 $f(3,4)=0,f(6,8)=1,f(12,16)=2$

现在给出一个包含 $n$ 个数的序列，请求出 $f(a_i,a_j)$ 的最大值，其中 $1\leq i < j \leq n$

输入格式

第一行，只包含一个正整数 $n$，表示序列中的元素个数

第二行，$n$ 个空格隔开的正整数，依次表示 $a_1,a_2,\cdots,a_n$

输出格式

一行，只包含一个非负整数表示答案

数据范围

设 $B$ 为一正整数，对于每个测试点，$2 \leq n \leq B$，$1 \leq a_1, a_2,\cdots,a_n \leq B$

对于$25\%$的数据，$B=300$

对于$50\%$的数据，$B=5000$

对于$100\%$的数据，$B=1000000$

5
1 2 3 4 5

1