A8821. Almost Arithmetical Progression

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_{1}=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_{1},s_{2},...,s_{k}$ is a subsequence of sequence $b_{1},b_{2},...,b_{n}$ , if there is such increasing sequence of indexes $i_{1},i_{2},...,i_{k}$ $(1<=i_{1}<i_{2}<...\ <i_{k}<=n)$ , that $b_{ij}=s_{j}$ . In other words, sequence $s$ can be obtained from $b$ by crossing out some elements.

The first line contains integer $n$ $(1<=n<=4000)$ . The next line contains $n$ integers $b_{1},b_{2},...,b_{n}$ $(1<=b_{i}<=10^{6})$ .

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

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

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