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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.StringTokenizer;

public class P255C
{
	public static void main(String[] args)
	{
		FastScanner scan = new FastScanner();
		int n = scan.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = scan.nextInt();
		ArrayList<Integer> list = new ArrayList<>();
		HashSet<Integer> set = new HashSet<>();
		HashMap<Integer, Integer> occur = new HashMap<>();
		for (int i = 0; i < n; i++)
		{
			if (!occur.containsKey(arr[i]))
				occur.put(arr[i], 1);
			else
				occur.put(arr[i], occur.get(arr[i])+1);
			if (!set.contains(arr[i]))
			{
				list.add(arr[i]);
				set.add(arr[i]);
			}
		}
		int max = 1;
		for (int i = 0; i < list.size(); i++)
		{
			int num = list.get(i);
			if (max >= 2*occur.get(num))
				continue;
			HashMap<Integer, Integer> map = new HashMap<>();
			set = new HashSet<>();
			int occ = 0;
			boolean start = false;
			for (int j = 0; j < n; j++)
			{
				if (arr[j] == num)
				{
					start = true;
					occ++;
					set = new HashSet<>();
					continue;
				}
				if (!start)
					continue;
				if (!set.contains(arr[j]))
				{
					if (!map.containsKey(arr[j]))
						map.put(arr[j], 1);
					else
						map.put(arr[j], map.get(arr[j])+1);
					set.add(arr[j]);
				}
			}
			for (Map.Entry<Integer, Integer> en : map.entrySet())
			{
				int f = en.getValue();
				int total = f;
				if (set.contains(en.getKey()))
					total += Math.min(occ, f); //should always be f?
				else
					total += Math.min(occ, f+1);
				max = Math.max(max, total);
			}
			max = Math.max(max, occ);
		}
		PrintWriter pw = new PrintWriter(System.out);
		pw.println(max);
		pw.flush();
	}
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner()
		{
			try
			{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
		}

		public String next()
		{
			if (st.hasMoreTokens())
				return st.nextToken();
			try
			{
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return st.nextToken();
		}

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

		public long nextLong()
		{
			return Long.parseLong(next());
		}

		public String nextLine()
		{
			String line = "";
			try
			{
				line = br.readLine();
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return line;
		}
	}
}
