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.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        int n=Integer.parseInt(br.readLine());
        int arr[]=new int[n];
        String str[]=br.readLine().split(" ");
        for(int i=0;i<n;i++)
        arr[i]=Integer.parseInt(str[i]);
        if(n<=2)
        pw.println(n);
        else
        {
            int mx=(int)1e6+1;
            int cntr[]=new int[mx];
            for(int i=0;i<n;i++)
            cntr[arr[i]]++;
            int ans=2;
            for(int i=1;i<mx;i++)
            ans=Math.max(ans,cntr[i]);
            cntr=new int[mx];
            int prev[]=new int[mx];
            for(int i=0;i<n;i++)
            {
                //HashMap<String,Integer> freq=new HashMap<>();
                //HashSet<String> hs=new HashSet<>();
                int maxtillNow=0;
                boolean b=false;
                int previous=-1;
                for(int j=i+1;j<n;j++)
                {
                    if(arr[j]==arr[i])
                    {
                        previous++;
                        ans=Math.max(maxtillNow+1,ans);
                    }
                    else if(previous!=prev[arr[j]])
                    {
                        //hmap.put(arr[i]+" "+arr[k],hmap.getOrDefault(arr[i]+" "+arr[k],0)+1);
                        //freq.put(arr[i]+" "+arr[j],freq.getOrDefault(arr[i]+" "+arr[j],0)+1);
                        cntr[arr[j]]++;
                        maxtillNow=Math.max(maxtillNow,cntr[arr[j]]*2);
                        ans=Math.max(ans,maxtillNow);
                        //hs.add(arr[i]+" "+arr[j]);
                        prev[arr[j]]=previous;
                    }
                }
                for(int j=i+1;j<n;j++)
                prev[arr[j]]=cntr[arr[j]]=0;
            }
            pw.println(ans);
        }
        pw.flush();
        pw.close();
    }
}