题目描述

等差数列是指从第二项起每一项与它的前一项的差等于同一个常数的一种数列。例如数列 $1, 4, 7, 10$ 就是满足首项为 $1$、公差为 $3$ 的等差数列。数列 $10, 7, 4, 1$ 就是满足首项为 $10$、公差为 $-3$ 的等差数列。

给定一个长度为 $N$ 的任意数列 $a_1, a_2, a_3, \ldots, a_n$，定义该数列中取出任意连续的长度 $\ge 3$ 的子段为该数列的子数列。请编程求出该数列中最长等差子数列的长度。如果不存在等差子序列，输出 $0$。

举例：$1, 4, 7, 2, 5, 1, -3, -7$ 这个序列，最长等差子序列为 $5, 1, -3, -7$ 这段，长度为 $4$。

输入格式

第 $1$ 行读入一个整数 $N$。

第 $2$ 行读入 $N$ 个整数，数字之间用空格隔开。

输出格式

输出该数列中能找到的最长等差子数列的长度。

20
-14 -8 -17 -1 -3 -5 -7 -9 -1 -4 -6 -8 -13 19 16 13 10 7 4 1

7

样例解释

最长等差子数列为 $19, 16, 13, 10, 7, 4, 1$，公差为 $-3$，长度为 $7$。

数据范围

$N \le 10^5$。