Arithmetic Progression

Problem Source

Click here

Problem Description

Given a set $S$ of size $n$, you may choose some elements from it to form an arithmetic progression. Find the length of the longest arithmetic progression.

Input Format

One line containing an integer $n\le 5000$.

The next line contains $n$ integers $|S_i| < 2^{31}$ describing the elements of the set $S$.

Output Format

One line containing an integer: the length of the longest arithmetic progression.

Sample Input

10
14 1 3 5 6 8 9 10 12 13

Sample Output

5

Sample Explanation

The arithmetic progressions (those with only two terms are omitted) include:

1 3 5

1 5 9 13

3 6 9 12

3 8 13

5 9 13

6 8 10 12 14

Among them, 6 8 10 12 14 is the longest, of length 5.