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.
//package tets;
import java.util.*;
import java.io.*;
public class Cf {

	static BufferedReader br;
	private static int getInt() throws NumberFormatException, IOException {
		int num=Integer.parseInt(br.readLine());
		return num;
	}
	
	private static int[] getArray() throws NumberFormatException,IOException{
		
		String[]T=br.readLine().split(" ");
		
		int[]A=new int[T.length];
		
		for(int i=0;i<A.length;i++) {
			A[i]=Integer.parseInt(T[i]);
		}
		
		return A;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		br=new BufferedReader(new InputStreamReader(System.in));

		int n=getInt();
		
		int[]A=getArray();
		
		HashMap<Integer,Integer>id=new HashMap<>();
		
		int k=0;
		for(int i=0;i<A.length;i++) {
			if(id.containsKey(A[i]))
			{
				A[i]=id.get(A[i]);
			}
			else
			{
				id.put(A[i],k);
				A[i]=k;
				k++;
			}
		}
		int ans=1;
		int[][]dp=new int[A.length][A.length];
		//0 1 0 1
		for(int i=0;i<A.length;i++) {
			
			for(int j=0;j<i;j++) {
				
			  int a=1+dp[j][A[i]];
			  int b=dp[i][A[j]];
			  dp[i][A[j]]=Math.max(a,b);
				
			 ans=Math.max(ans,1+dp[i][A[j]]);
			}
			
		}
		
		System.out.println(ans);
	}

}
