Almost Arithmetical Progression

1000ms

262144K

Description:

Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:

a₁ = p, where p is some integer;
a_i = a_i - 1 + ( - 1)^i + 1·q (i > 1), where q is some integer.

Right now Gena has a piece of paper with sequence b, consisting of n integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

Sequence s₁, s₂, ..., s_k is a subsequence of sequence b₁, b₂, ..., b_n, if there is such increasing sequence of indexes i₁, i₂, ..., i_k (1 ≤ i₁ < i₂ < ... < i_k ≤ n), that b_{i_j} = s_j. In other words, sequence s can be obtained from b by crossing out some elements.

Input:

The first line contains integer n (1 ≤ n ≤ 4000). The next line contains n integers b₁, b₂, ..., b_n (1 ≤ b_i ≤ 10⁶).

Output:

Print a single integer — the length of the required longest subsequence.

Sample Input:

2
3 5

Sample Output:

Sample Input:

4
10 20 10 30

Sample Output:

Note:

In the first test the sequence actually is the suitable subsequence.

In the second test the following subsequence fits: 10, 20, 10.

Informação

Provedor Codeforces

Código CF255C