题目描述

给定一个序列：1，4，3，5，7

显然子序列：“1，3，5，7” 是一个等差数列。

给定一个序列，求最长的等差子序列，显然这个子序列中 元素的前后关系要与原序列保持一致。

输入格式

第一行，一个整数N。

第二行，N个整数 $a_i$。

输出格式

题目要求的最长长度。

样例数据

input

5

1

4

3

5

7

output

4

数据规模与约定

100% 数据保证 $1 \leq N \leq 2000, 1 \leq a_i \leq 10^9$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$