有一个长度为 $n$ 的数组 $a$，第 $i$ 个位置是 $a_i$。

我们现在需要找到一个最长的区间 $[l,r]$ 满足：存在一个整数 $m\geq 2$，使得区间内所有数字 $a_i(l\leq i\leq r)$ 都满足 $a_i\mod m$ 全相等。

输出这个最长的区间长度即可。

输入格式

第一行输入 $n$，第二行输入 $n$ 个正整数 $a_1,...,a_n$。

输出格式

输出一个数字代表答案。

5
1 5 2 4 6

3

4
8 2 5 10

3

8
465 55 3 54 234 12 45 78

6

数据范围

对于 $20\%$ 的数据：$n\leq 300,1\leq a_i\leq 1000$。

对于 $40\%$ 的数据：$n\leq 2\times 10^4,1\leq a_i\leq 1000$。

对于 $70\%$ 的数据：$n\leq 2\times 10^5$。

对于 $100\%$ 的数据：$n\leq 2\times 10^6,1\leq a_i\leq 10^{18}$。