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:

  * a1 = p, where p is some integer; 
  * ai = ai - 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 s1, s2, ..., sk is a subsequence of sequence b1, b2, ..., bn, if there is such increasing sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), that bij = sj. 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 b1, b2, ..., bn (1 ≤ bi ≤ 106).

Output

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

Examples

Input

2
3 5


Output

2


Input

4
10 20 10 30


Output

3

Note

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

In the second test the following subsequence fits: 10, 20, 10.
import java.io.*;
import java.util.*;
public class C255
{
    public static void main(String args[])throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String s[]=br.readLine().split(" ");
        int arr[]=new int[n];int maxnum=0;
        for(int i=0;i<n;i++)
        {
            arr[i]=Integer.parseInt(s[i]);
            maxnum=(int)(Math.max(maxnum,arr[i]));
        }
        int max=1;
        int count[]=new int[maxnum+1];
        int ind[]=new int[maxnum+1];
        for(int i=0;i<n;i++)
        {
            int last=i;count[arr[i]]+=1;
            for(int j=i+1;j<n;j++)
            {
                if(arr[j]==arr[i])
                {
                    last=j;
                    count[arr[j]]+=1;
                    ind[arr[j]]=j;
                }
                else
                {
                    if(ind[arr[j]]==0)
                    {
                        ind[arr[j]]=j;
                        count[arr[j]]=2;
                    }
                    else
                    {
                        if(last>ind[arr[j]])
                        {
                           count[arr[j]]+=2;
                           ind[arr[j]]=j;
                        }
                    }
                }
            }
            for(int j=i;j<n;j++)
            {
                if(last>ind[arr[j]])
                {
                    max=(int)(Math.max(max,count[arr[j]]+1));
                }
                else
                {
                    max=(int)(Math.max(max,count[arr[j]]));
                }
                count[arr[j]]=0;
                ind[arr[j]]=0;
            }
        }
        System.out.println(max);
    }
}