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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class AlmostArithmeticalProgression
{
	static int[][] s = new int[4000][4000];
	static int k = 0;
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		
		
		for (int i = 0; i < arr.length; i++)
			arr[i] = sc.nextInt();
		
		
		int max = 1;

		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for (int i = arr.length - 1; i >= 0; i--)
		{
			for (int j = i+1; j < arr.length; j++)
			{
				int x, y;
				if(map.get(arr[i]) == null)
				{
					x = k;
					map.put(arr[i], k++);
				}
				else
					x = map.get(arr[i]);
				
				if(map.get(arr[j]) == null)
				{
					y = k;
					map.put(arr[j], k++);
				}
				else
					y = map.get(arr[j]);
				
				
				if(y != x)
				{
					int aa = s[y][x];
					if(aa == 0)
					{
						s[x][y] = 2;
						max = Math.max(max, 2);
					}
					else
					{
						s[x][y] = aa+1;
						max = Math.max(max, aa+1);
					}
					
				}
			}
		}
		
		int dupl = 0;
		for (int i = 0; i < arr.length; i++)
		{
			dupl = 0;
			for (int j = i; j < arr.length; j++)
			{
				if(arr[i] == arr[j])
					dupl++;
			}
			max = Math.max(dupl, max);
		}
		
		System.out.println(max);
	}
	
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

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

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}
}
