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*_{*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*_{1}, *b*_{2}, ..., *b*_{*n*}$ $(1 ≤ *b*_{*i*} ≤ 10^{6})$.

Output

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

Note

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

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