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.awt.List;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;

public class Watermelon2 {
	public static void main(String[] args) throws IOException{
		Main2 m=new Main2();
		m.solve();
	}
	}
class Main2{
	
	 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	 private int[] array;
	    private int[] tempMergArr;
	    private int length;
	
	    BigInteger[] temp=new BigInteger[31];
		BigInteger x,y,z;
	    StringTokenizer stringTokenizer;

	     String next() throws IOException {
	        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
	            stringTokenizer = new StringTokenizer(reader.readLine());
	        }
	        return stringTokenizer.nextToken();
	    }

	    int nextInt() throws IOException {
	        return Integer.parseInt(next());
	    }

	    long nextLong() throws IOException {
	        return Long.parseLong(next());
	    }
	    int marr[]=null;
	    void solve() throws IOException  {
	    	int n=this.nextInt();
	        int[][] arr=new int[n+1][n+1];
	        int[] marr=new int[n+1];
	        for(int i=1;i<=n;i++)
	        	marr[i]=this.nextInt();
	        int pr=0;
	        arr[0][0]=0;
	        int res=0;
	        for(int i=1;i<=n;i++){
	        	pr=0;
	        	for(int j=0;j<i;j++){
	        	arr[j][i]=arr[pr][j]+1;
	        	if(marr[j]==marr[i])pr=j;
	        	res=Math.max(res, arr[j][i]);
	        	}
	        }
	        System.out.println(res);
	 }
	    
	    public String recurs(char[] carr,int k){
	    	int count=0;
	    	for(int i=0;i<carr.length;i++){
	    		if(i+k-1<carr.length)
	    		if(carr[i]=='-'){
	    			for(int j=i;j<i+k;j++){
	    				
	    				if(carr[j]=='+')
	    					{carr[j]='-';continue;}
	    				if(carr[j]=='-')
	    					{carr[j]='+';continue;}
	    		//		System.out.println(j+" "+i+" "+carr[j]);
	    			}
	    			count++;
	    			
	    		}
	    	//	display(carr);
	    	}
	    	for(int i=0;i<carr.length;i++){
	    		if(carr[i]=='-')
	    			return "IMPOSSIBLE";
	    	}
	    	return Integer.toString(count);
	    }
	    static int max_LIS=0;
	    public int LIS(int[] arr,int n){
	    	if(n==0)
	    		{
	    		marr[0]=1;
	    		return 1;
	    		}
	    	
	    	int current =1;
	    	for(int i=0;i<n;i++){
	    		int subproblem=0;
	    		if(marr[i]==0)
	    		{
	    			subproblem=LIS(arr,i);
	    			marr[i]=subproblem;
	    		}
	    		else{
	    		//	System.out.println("Hey");
	    			subproblem=marr[i];
	    		}
	    		
	    		System.out.println(current+" "+subproblem+" "+i);
	    		if(arr[i]<arr[n]&&current<(1+subproblem)){
	    			current=(1+subproblem);
	    		}
	    	}
	    	if(max_LIS<current)
	    		max_LIS=current;
	    	return current;
	    }
	    
	public BigInteger comb(int n,int r){
	     x=this.temp[n];
		 y=this.temp[r];
		 z=this.temp[n-r];
	//	 System.out.println(x+" "+y+" "+z);
		 BigInteger ret=x.divide(y.multiply(z));
		 return ret;
		 
	}
	public void fact(){
		this.temp[0]=BigInteger.ONE;
		this.temp[1]=BigInteger.ONE;
		for(int i=2;i<this.temp.length;i++){
			temp[i]=(temp[i-1].multiply(BigInteger.valueOf(i)));
		}
	}
	private static int gcd(int a, int b)
	{
	    while (b > 0)
	    {
	    	int temp = b;
	        b = a % b; // % is remainder
	        a = temp;
	    }
	    return a;
	}
	private static int lcm(int a, int b)
	{
	    return a * (b / gcd(a, b));
	}
	static int[] toFractionPos(int x,int y){
		int a=gcd(x,y);
		int[] arr={x/a,y/a};
		//display(arr);
		return arr;
	}
   
	static void display(double[][] arr){
		
		for(int i=0;i<arr.length;i++){
			for(int j=0;j<arr[i].length;j++){
				System.out.print(arr[i][j]+" ");
		}
		System.out.println();
		}
	System.out.println();
	}

	 static void display(String[] arr){
			for(int i=0;i<arr.length;i++){
				System.out.println(arr[i]+" ");
			}	
			//System.out.println();
		
	 }
	 static void display(int[] arr){
		 for(int i=0;i<arr.length;i++)
				System.out.print(arr[i]+" ");
		System.out.println();
		 }
		 static void display(double[] arr){
		 	   for(int i=0;i<arr.length;i++){
		 		   System.out.print(arr[i]+" ");
		 	   }
		 	   System.out.println();
	    }
	 static void display(char[] arr){
		// System.out.println();
		 int t=0;
			for(int i=0;i<arr.length;i++){
				if(arr[i]!='0'){t=i;break;}
			}	
			while(t!=arr.length){
				System.out.print(arr[t]);
				t++;
			}
			System.out.println();
		
		  }
	 static String str(char[] carr){
		 String str="";
		 for(int i=0;i<carr.length;i++){
			    str=str+carr[i];
			}
		 return str;
	 }
	    public void sort(int inputArr[]) {
	        this.array = inputArr;
	        this.length = inputArr.length;
	        this.tempMergArr = new int[length];
	        doMergeSort(0, length - 1);
	    }
	 
	    private void doMergeSort(int lowerIndex, int higherIndex) {
	         
	        if (lowerIndex < higherIndex) {
	            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
	            // Below step sorts the left side of the array
	            doMergeSort(lowerIndex, middle);
	            // Below step sorts the right side of the array
	            doMergeSort(middle + 1, higherIndex);
	            // Now merge both sides
	            mergeParts(lowerIndex, middle, higherIndex);
	        }
	    }
	 
	    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
	 
	        for (int i = lowerIndex; i <= higherIndex; i++) {
	            tempMergArr[i] = array[i];
	        }
	        int i = lowerIndex;
	        int j = middle + 1;
	        int k = lowerIndex;
	        while (i <= middle && j <= higherIndex) {
	            if (tempMergArr[i] <= tempMergArr[j]) {
	                array[k] = tempMergArr[i];
	                i++;
	            } else {
	                array[k] = tempMergArr[j];
	                j++;
	            }
	            k++;
	        }
	        while (i <= middle) {
	            array[k] = tempMergArr[i];
	            k++;
	            i++;
	        }
	 
	    }
}


 class  Count2 implements Comparable {
    	    Integer i;
    	    Integer j;
            Integer k;
    	    Count2(int i,int j){
    	        this.j=j;
    	        this.i=i;
    	        this.k=i;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j+" "+k);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Count2 c=(Count2)o;
    			if(i.compareTo(c.i)>0)
    				return 1;
    			else if(i.compareTo(c.i)<0)
    				return -1;
    			else{
    				return 0;
    				
    			}
    		}
    		
    	}

 class  Counti2 implements Comparable {
    	    Integer i;
    	    int j;
    	    int k;
    	    Counti2(int i,int j,int k){
    	        this.j=j;
    	        this.i=i;
    	        this.k=k;
    	    }
    	    void display(){
    	    	System.out.println(i+" "+j+" "+k);
    	    }
    	    
    	    	@Override
    		public int compareTo(Object o) {
    			// TODO Auto-generated method stub
    			Counti2 c=(Counti2)o;
    			if(i.compareTo(c.i)>0)
    				return 1;
    			else if(i.compareTo(c.i)<0)
    	    		return -1;
    			else
    				return 0;
    		}
    		
    	}
		
 class Extra2{
	 ArrayList<Integer> list=new ArrayList<>();
	 Extra2(int i){
		 list.add(i);
	 }
	 void display(){
		 System.out.println(list.size());
		 for(int i=0;i<list.size();i++){
			 System.out.print(list.get(i)+" ");
		 }
		 System.out.println();
	 }
 }