Arithmetic Progressions

Interview

Time limit5sMemory limit512 MB

Summary

Given up to 5000 distinct numbers, find the length of the longest subset that forms an arithmetic progression.

Level: Medium6 of 10
Topics: Array, Hash map, Dynamic programming
Solved: No attempts yet

Problem

An arithmetic progression is a sequence $a_1, a_2, \dots, a_k$ in which the difference of consecutive terms $a_{i+1} - a_i$ is constant ( $1 \le i \le k-1$ ). For example, the sequence 5, 8, 11, 14, 17 is an arithmetic progression of length 5 with common difference 3.

In this problem, you must find the length of the longest arithmetic progression that can be formed by selecting some numbers from a given set of numbers. For example, if the given set is $\{0, 1, 3, 5, 6, 9\}$ , you can form progressions such as 0, 3, 6, 9 with common difference 3, or 9, 5, 1 with common difference $-4$ . Here 0, 3, 6, 9 and 9, 6, 3, 0 are the longest.

Input

The input consists of a single test case in the following format.

n
v1 v2 ··· vn

$n$ is the number of elements in the set, an integer satisfying $2 \le n \le 5000$ . Each $v_i$ ( $1 \le i \le n$ ) is an element of the set, an integer satisfying $0 \le v_i \le 10^9$ . All $v_i$ are distinct, that is, $v_i \ne v_j$ if $i \ne j$ .

Output

Output the length of the longest arithmetic progression that can be formed by selecting some numbers from the given set.

Examples3

Example 1
Input
```
6
0 1 3 5 6 9
```
Expected output
```
4
```
Example 2
Input
```
7
1 4 7 3 2 6 5
```
Expected output
```
7
```
Example 3
Input
```
5
1 2 4 8 16
```
Expected output
```
2
```