题目描述

给定一个整数序列，求最长等差数列子序列的长度。

输入格式

第一行一个整数n，第二行n个整数。

输出格式

输出最长长度。

样例数据

input

8
1 4 2 5 3 6 7 9

output

4

数据范围

 1≤n≤10000，元素绝对值≤1e3。