该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目：等差子数列

题目描述

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

给定一个长度为 $N$ 的任意数列 $a_1, a_2, a_3, \dots, a_n$，定义该数列中取出任意连续的、长度 $\geq 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  

• 输出

7  

• 解释：从第 14 个数到第 20 个数（19 16 13 10 7 4 1 ）构成公差为 -3、长度为 7 的等差数列。
• 样例 2
  • 输入

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

• 输出

3  

• 样例 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 的等差数列。
• 数据范围
  • 测试点 1 ~ 6： $3 \leq N \leq 1000$
  • 测试点 7 ~ 10： $3 \leq N \leq 100000$， $-10^5 \leq a_i \leq 10^5$