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 AlmostProgression2 {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(rd.readLine());
		A = new int[N];
		last = new int[N][N];
		StringTokenizer st = new StringTokenizer(rd.readLine());
		for(int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());
		magic();
		HashMap<Integer, Short> map = new HashMap<Integer, Short>();
		int max = 0;
		HashSet<Integer> seen = new HashSet<Integer>();
		
		for(int i=0; i<N; i++){
			int c = A[i];
			Short freq = map.get(c);
			short newFreq = freq==null? 1: (short) (freq+1);
			max = Math.max(max, newFreq);
			map.put(c, newFreq);
		}
		for(int i=0; i<N; i++){
			if(!seen.contains(A[i])){
				max = Math.max(max, countFor(i));
				seen.add(A[i]);
			}
		}
		System.out.println(max);
	}
	
	static void magic(){
		int numb = 0;
		B = new int[N];
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i=0; i<N; i++){
			int cur = A[i];
			if(!map.containsKey(cur)){
				map.put(cur, numb++);
				B[i] = numb-1;
			}
			else{
				B[i] = map.get(cur);
			}
		}
		for(int i=0; i<N; i++) A[i] = B[i];
	}
	
	static int[][] last;
	static int[] B;
	
	static int countFor(int index){
		HashMap<Integer, Short> freqMap = new HashMap<Integer, Short>();
		//HashMap<Integer, Integer> last = new HashMap<Integer, Integer>();
		int lastA = index;
		for(int i=index+1; i<N; i++){
			int cur = A[i];
			if(cur==A[index]){
				//cantTake.clear();
				lastA = i;
			}
			else{
	//			if(cantTake.contains(cur)) continue;
	//			if(!freqMap.containsKey(cur)) freqMap.put(cur, (short)1);
	//			else freqMap.put(cur, (short) (1+freqMap.get(cur)));
				if(last[index][cur]==0){
					last[index][cur] = i;
					freqMap.put(cur, (short)1);
				}
				else{
					int l = last[index][cur];
					if(lastA<l){
						last[index][cur] = i;
						continue;
					}
					Short res = freqMap.get(cur);
					short newF = res==null? 1: (short) (1+res);
					freqMap.put(cur, newF);
					last[index][cur] = i;
				}
		//		cantTake.add(cur);
			}
		}
		int max = 0;
		Iterator<Integer> iter = freqMap.keySet().iterator();
		while(iter.hasNext()){
			int cur = iter.next();
			int val = freqMap.get(cur)*2;
			if(last[index][cur]<lastA) val++;
			max = Math.max(max, val);
		}
//		System.out.println(max+" "+index);
		return max;
	}
	
	static int[] A;
	static int N;
	
}
