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.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;



public class Abood2C {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();

		int[] a = new int[n];
		HashSet<Integer> s = new HashSet<>();
		for (int i = 0; i < n; ++i)
			s.add(a[i] = sc.nextInt());

		if(s.size() == n){
			System.out.println(Math.min(n, 2));
			return;
		}

		int[] last = new int[n];
		int ans = 0;

		for (int i = 0; i < n; i++) {
			last[i] = -1;
			int c = 1;
			for (int j = i - 1; j >= 0; j--) {
				if(a[i] == a[j]) {
					if(last[i] == -1)
						last[i] = j;
					c++;
				}
			}
			ans = Math.max(c, ans);
		}
//		System.out.println(Arrays.toString(last));
		for (Integer y : s) {
			int[] p = new int[n + 1];
			Arrays.fill(p, -1);
			int[] dp = new int[n];
			boolean f1 = false, f2 = false;

			int lastY = -1;
			for (int i = 0; i < n; i++) {
				if(a[i] == y){
					f1 = true;
					lastY = i;
				}else
					f2 = true;

				if(a[i] == y) {
					if(last[i] == -1) {
						if(f2)
							dp[i] = 2;
						else
							dp[i] = 1;
					}else {
						int c = dp[last[i]];
						if(p[c + 1] > last[i])
							dp[i] = c + 2;
						else if(p[c] > last[i])
							dp[i] = c + 1;
						else
							dp[i] = c;
					}
				}else {
					if(last[i] == -1) {
						if(f1)
							dp[i] = 2;
						else
							dp[i] = 1;
					}else {
						if(lastY > last[i])
							dp[i] = dp[last[i]] + 2;
						else
							dp[i] = dp[last[i]];
					}
				}
				ans = Math.max(dp[i], ans);
				p[dp[i]] = i;
			}
			
//			System.out.println(y + " " + Arrays.toString(dp));
		}

		out.println(ans);

		out.flush();
		out.close();
	}




	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();}



	}

}