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.*;
import java.util.*;

public class Solution{
	InputStream is;
	static PrintWriter out;
	String INPUT = "";
	static long mod = (long)1e9+7L;
	
	public void solve(){
		int n = ni();
		int[] a = new int[n];
		TreeSet<Integer> set = new TreeSet<Integer>();
		ArrayList<Integer> list = new ArrayList<>();
		HashMap<Integer, Integer> map = new HashMap<>();

		int v = 0;
		for(int i = 0; i < n; i++){
			a[i] = ni();
			if(!map.containsKey(a[i])){
				map.put(a[i], v);
				v = v+1;
			}

			a[i] = map.get(a[i]);
			set.add(a[i]);
		}

		int ans = 1;
		map.clear();
		for(int i = 0; i < n; i++){
			if(!map.containsKey(a[i])){
				map.put(a[i], 1);
			}
			else{
				map.put(a[i], map.get(a[i])+1);
			}
		}
		for(int i = 0; i < n; i++){
			ans = Math.max(ans, map.get(a[i]));
		}

//out.println(Arrays.toString(a));
		for(int i = 0; i < v; i++){
//out.println(ans);
			ArrayList<Pair> al = new ArrayList<>();
			int l = 0;
			for(int j = 0; j < n; j++){
				if(a[j] == i){
					al.add(new Pair(l, j));
					l = j;
				}
			}
			al.add(new Pair(l, n-1));
//out.println(i+" "+al);
			int[] pos = new int[n];
			Arrays.fill(pos, -1);
			int[] size = new int[n];
			boolean[] first = new boolean[n];
			boolean[] last = new boolean[n];
			for(int j = 0; j < al.size(); j++){
				Pair p = al.get(j);
				for(int k = p.fs; k <= p.sc; k++){
					if(a[k] != i && pos[a[k]] < j){
						pos[a[k]] = j;
						size[a[k]] +=1;

						if(j == 0){
							first[a[k]] = true;
						}
						if(j == al.size()-1){
							last[a[k]] = true;
						}
					}
				}
			}
//out.println(Arrays.toString(size));
			for(int j = 0; j < n; j++){
				if(first[j] && last[j]){
					ans = Math.max(ans, 2*(size[j]-1) + 1);
				}
				else if(first[j] || last[j]){
					ans = Math.max(ans, 2*size[j]);
				}
				else{
					ans = Math.max(ans, 2*size[j] + 1);
				}
			}
		}

		out.println(ans);
	}

	void run(){
		is = new DataInputStream(System.in);
		out = new PrintWriter(System.out);
		int t=1;while(t-->0)solve();
		out.flush();
	}
	public static void main(String[] args)throws Exception{new Solution().run();}
	long mod(long v, long m){if(v<0){long q=(Math.abs(v)+m-1L)/m;v=v+q*m;}return v%m;}
    long mod(long v){if(v<0){long q=(Math.abs(v)+mod-1L)/mod;v=v+q*mod;}return v%mod;}
	//Fast I/O code is copied from uwi code.
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	private int readByte(){
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	private String ns(){
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	private char[] ns(int n){
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	private char[][] nm(int n, int m){
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	private int[] na(int n){
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	private int ni(){
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	private long nl(){
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	static  int i(long x){return (int)Math.round(x);}
	static class Pair implements Comparable<Pair>{
		int fs,sc;
		Pair(int a, int b){
			fs=a;
			sc=b;
		}
		public int compareTo(Pair p){
			if(this.fs>p.fs)return 1;
			else if(this.fs<p.fs)return -1;
			else{
				return i(this.sc-p.sc);
			}
			//return i(this.sc-p.sc);
		}
		public String toString(){
			return "("+fs+","+sc+")";
		}	
	}
	
}