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.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static int[] array;
	public static node[] nodes;

	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(f.readLine());
		StringTokenizer st = new StringTokenizer(f.readLine());
		array = new int[N + 1];
		nodes = new node[N + 1];
		for (int i = 1; i <= N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		nodes[0] = new node(-1 << 29, -1 << 29);
		for (int i = 1; i <= N; i++) {
			nodes[i] = new node(i, array[i]);
		}
		Arrays.sort(nodes);
		int curr = 1;
		for (int i = 1; i <= N; i++) {
			if (i != 1 && nodes[i].value != nodes[i - 1].value) {
				curr++;
			}
			array[nodes[i].index] = curr;
		}
		int[] indexes = new int[N + 5];
		int[] last = new int[N + 1];
		int[] counts = new int[N + 5];
		for (int i = 1; i <= N; i++) {
			last[i] = indexes[array[i]];
			indexes[array[i]] = i;
			counts[array[i]]++;
		}
		int res = 0;
		for (int i : counts) {
			res = Math.max(res, i);
		}
		int[][] dp = new int[N + 5][N + 5];
		for (int i = 1; i <= N; i++) {
			dp[i][0] = 1;
			for (int j = 1; j <= last[i]; j++) {
				dp[i][j] = dp[last[i]][j];
			}
			for (int j = last[i] + 1; j < i; j++) {
				int temp = last[j];
				while (temp > last[i]) {
					temp = last[temp];
				}
				dp[i][j] = dp[last[i]][temp] + 2;
				res = Math.max(res, dp[i][j]);
			}
		}
		System.out.println(res);
	}

	public static void printArray(int[] array) {
		for (int i : array) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void printMatrix(int[][] matrix) {
		for (int[] is : matrix) {
			printArray(is);
		}
		System.out.println();
	}
}

class node implements Comparable<node> {
	public int index, value;

	public node(int a, int b) {
		index = a;
		value = b;
	}

	public int compareTo(node next) {
		return value - next.value;
	}
}