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.*;
import java.math.*;
 
public class Almost_Arithmetical_Progression {
 
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw=new PrintWriter(System.out);

		int t=1;

		while(t-->0)
		{

			int n=Integer.parseInt(br.readLine());

			String str[]=br.readLine().trim().split(" ");

			int a[]=new int[n];

			for(int i=0;i<n;i++)
				a[i]=Integer.parseInt(str[i]);

			HashMap<Integer,Integer> mp=new HashMap<>();

			int index=-1;

			for(int i=0;i<n;i++)
			{
				if(mp.get(a[i])==null)
					mp.put(a[i],++index);
			}

			for(int i=0;i<n;i++)
				a[i]=mp.get(a[i]);

			int dp[][]=new int[n][n];

			for(int i=0;i<n;i++)
			{
				Arrays.fill(dp[i],1);
			}

			/*for(int x:a)
				System.out.print(x+" ");
			System.out.println();*/

			long ans=1;
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<i;j++)
				{
					dp[i][a[j]]=Math.max(1+dp[j][a[i]],dp[i][a[j]]);
					ans=Math.max(ans,dp[i][a[j]]);
				}
			}

			/*for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
				{
					System.out.print(dp[i][j]+" ");
				}
				System.out.println();
			}*/


			pw.println(ans);
		}
		pw.flush();
	}

}