Longest Arithmetic Progression

An arithmetic progression is an ascending sequence $a_1 < a_2 < \dots < a_n$ in which the difference between two consecutive elements is always the same. For example, $11 < 21 < 31 < 41 < 51$ is an arithmetic progression.

A subsequence of an ascending sequence $a$ of $n$ numbers is an ascending sequence $b_1 < b_2 < \dots < b_m$ with $m \le n$ whose elements all occur in $a$. For example, $21 < 41 < 51$, $11 < 41$, and $11 < 21 < 31 < 41 < 51$ are subsequences of $11 < 21 < 31 < 41 < 51$.

You are given an ascending sequence $c_1 < c_2 < \dots < c_k$. Find the length of a longest arithmetic progression that is a subsequence of $c$. There may be several longest arithmetic progressions, but the length is unique.

A sequence of one element or two elements also satisfies the definition, so the answer is never smaller than 2.

$k$ is at least 10 and at most 500, and every element of $c$ is a positive integer smaller than 100000.

The input has two lines. The first line contains the number of elements $k$ of $c$. The second line contains the elements of $c$ in ascending order, separated by spaces.

Print, on one line, the length of the longest arithmetic progression that is a subsequence of $c$.