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.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class l034 {

	public static void main(String[] args) throws Exception {
//		StringTokenizer stok = new StringTokenizer(new Scanner(new File("F:/books/input.txt")).useDelimiter("\\A").next());
		StringTokenizer stok = new StringTokenizer(new Scanner(System.in).useDelimiter("\\A").next());
		StringBuilder sb = new StringBuilder();
		Integer n = Integer.parseInt(stok.nextToken());
		HashMap<Integer,ArrayList<Integer>> mp = new HashMap<Integer,ArrayList<Integer>>();
		ArrayList<Integer> kList = new ArrayList<Integer>();
		for(int i=0;i<n;i++) {
			int v = Integer.parseInt(stok.nextToken());
			ArrayList<Integer> list = mp.get(v);
			if(list==null) {
				list = new ArrayList<Integer>();
				kList.add(v);
			}
			list.add(i);
			mp.put(v, list);
		}
		int l = kList.size();
		long max = 1;
		for(int i=0;i<l;i++) { 
			int l1 = mp.get(kList.get(i)).size();
			max = Math.max(max, l1);
			if(l1*2<=max) continue;
			for(int j=i+1;j<l;j++) {
				int l2 = mp.get(kList.get(j)).size();
				max = Math.max(max, l2);
				if(Math.min(l1, l2)*2+1<=max) continue;
				max = Math.max(max, solve(mp,kList.get(i),kList.get(j),sb));
			}
		}
		System.out.println(max);
	}

	private static long solve(HashMap<Integer, ArrayList<Integer>> mp, 
			Integer ii, Integer jj, StringBuilder sb) {
		int x = ii,y=jj-ii;
		int o=1;
		long ret = 1;
		int k = x;
		int pos = mp.get(k).get(0);
		k=x+y;
		while(true) {
			pos = Collections.binarySearch(mp.get(k), pos);
			pos=-pos-1;
			if(pos<mp.get(k).size()) {
				ret++;
				pos = mp.get(k).get(pos);
			}
			else break;
			o^=1;
			k = x+o*y;
		}
//		if(ret>3)
//			sb.append(ii+" "+jj+" "+ret+"\n");
		return ret;
	}

}
