题目描述

等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列。

例如，数列：1 4 7 10，就是满足首项为 1，公差为 3的等差数列。数列：10 7 4 1 就是满足首项为 10 公差为 −3的等差数列。

给定一个长度为 N的任意数列a1,a2,a3...an，定义该数列中取出任意连续的长度≥3 的子段为该数列的子数列。

请编程求出，该数列中，最长等差子数列的长度。

输入格式

第 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

20
18 -5 -18 -11 -6 -12 3 15 2 -10 -6 -2 -9 9 11 13 -12 -1 9 19

3

17
-7 -7 -9 -18 18 -15 -7 -6 -18 -10 -14 -17 -7 -3 -10 -8 18

0

解释#1

从第 4个数到第 8 个数，构成长度为 5 的等差数列。

从第 10个数到第 12个数，构成长度为 3 的等差数列。

从第 14个数到第 20个数，构成长度为 7 的等差数列。

数据范围

• 对于 $60\%$ 的测试数据满足：$3≤N≤1000$。
• 对于 $100\%$ 的测试数据满足：$3≤N≤100000$，$-10^5≤Ai≤10^5$。