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.*;

public class Almost_Arithmetical_Progression {

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}

	public static void shuffle(int[] a) {
		Random r = new Random();

		for (int i = 0; i <= a.length - 2; i++) {
			int j = i + r.nextInt(a.length - i);

			swap(a, i, j);
		}

		Arrays.sort(a);
	}

	public static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader t = new FastReader();
		PrintWriter o = new PrintWriter(System.out);
		int max = 0;
		int n = t.nextInt();
		Map<Integer, List<Integer>> map = new HashMap<>();

		for (int i = 0; i < n; ++i) {
			int x = t.nextInt();
			List<Integer> list = map.getOrDefault(x, new ArrayList<>());

			list.add(i);
			map.put(x, list);
		}

		for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
			max = Math.max(max, m.getValue().size());

		for (Map.Entry<Integer, List<Integer>> m1 : map.entrySet())
			for (Map.Entry<Integer, List<Integer>> m2 : map.entrySet()) {
				if (m1.getKey() == m2.getKey())
					continue;

				List<Integer> l1 = m1.getValue();
				List<Integer> l2 = m2.getValue();
				int count = 0;
				int i = 0, j = 0;
				boolean turn = false;

				if (l1.get(0) > l2.get(0)) {
					turn = true;
				}

				while (i < l1.size() && j < l2.size()) {
					if (turn) {
						if (l2.get(j) < l1.get(i)) {
							turn = !turn;
							++count;
							++j;
						} else
							++i;
					} else {
						if (l1.get(i) < l2.get(j)) {
							turn = !turn;
							++count;
							++i;
						} else
							++j;
					}
				}

				while (turn && j < l2.size()) {
					if (l2.get(j) > l1.get(l1.size() - 1)) {
						++count;
						turn = false;
					}

					++j;
				}

				while (!turn && i < l1.size()) {
					if (l1.get(i) > l2.get(l2.size() - 1)) {
						++count;
						turn = true;
					}

					++i;
				}

				max = Math.max(max, count);
			}

		o.println(max);
		o.flush();
		o.close();
	}
}