当前没有测试数据。

等差子数列

题目描述

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

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

给定一个长度为 $N$ 的任意数列 $a_{1},a_{2},a_{3},…,a_{n}$，定义该数列中取出任意连续的长度$≥3$ 的子段为该数列的子数列。

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

输入

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

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

输出

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

样例

输入数据1

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

输出数据1

7

输入数据2

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

输出数据2

3

输入数据3

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

输出数据3

0

说明

样例 $1$ 解释

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

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

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

数据范围

测试点 $1∼6$ 满足，$3≤N≤1000$。

测试点 $7∼10$ 满足，$3≤N≤100000$，$−10^{5} ≤a_{i}≤10^{5}$。