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.IOException;
import java.util.HashSet;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.TreeSet;

public class AlmostArithmeticalProgression {
    public static void main(String[] args) {
        FasterScanner sc = new FasterScanner();
        
        int N = sc.nextInt();
        int[] B = sc.nextIntArray(N);
        
        TreeSet<Integer> ts = new TreeSet<Integer>();
        for (int num : B) {
        	ts.add(num);
        }
        
        int idx = 0;
        HashMap<Integer, Integer> mapDown = new HashMap<Integer, Integer>();
        for (int num : ts) {
        	mapDown.put(num, idx++);
        }
        
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
        	A[i] = mapDown.get(B[i]);
        }
        
//        int[][] freq = new int[N][N];
//        int[] sing = new int[N];
//        for (int i = 0; i < N; i++) {
//        	for (int j = 0; j < N; j++) {
//        		if (A[i] == j) {
//        			sing[A[i]]++;
//        		} else {
//        			if (freq[A[i]][j] % 2 == 0) {
//        				freq[A[i]][j]++;
//        			}
//        			if (freq[j][A[i]] % 2 == 1) {
//        				freq[j][A[i]]++;
//        			}
//        		}
//        	}
//        }
//        
//        int best = 0;
//        for (int i = 0; i < N; i++) {
//        	best = Math.max(best, sing[i]);
//        	for (int j = 0; j < N; j++) {
//        		best = Math.max(best, freq[i][j]);
//        	}
//        }
//        System.out.println(best);
        
        int best = 1;
        HashSet<Integer> used = new HashSet<Integer>();
        for (int init : A) {
        	if (used.contains(init)) {
        		continue;
        	}
            used.add(init);
            
        	int[] map = new int[N];
            HashSet<Integer> set = new HashSet<Integer>();
            int cnt = 0;
            for (int i = 0; i < N; i++) {
            	if (A[i] != init) {
            		set.add(A[i]);
            	} else {
            		addSetToMap(set, map, 2);
            		set = new HashSet<Integer>();
            		cnt++;
            	}
            }
            addSetToMap(set, map, 1);
            int mapMax = 0;
            
            for (int val : map) {
            	mapMax = Math.max(mapMax, val);
            }
            best = Math.max(best, Math.max(cnt, mapMax));
        }
        System.out.println(best);
    }
    
    public static void addSetToMap(HashSet<Integer> set, int[] map, int freq) {
		for (int num : set) {
			map[num] += freq;
		}
    }
    
    public static class CountMap extends HashMap<Integer, Integer> {
		private static final long serialVersionUID = -5100883664402929579L;
    	
		public int getCount(int k) {
			return this.containsKey(k) ? this.get(k) : 0;
		}
		
		public void addCount(int k, int v) {
			this.put(k, this.getCount(k) + v);
		}
    }
    
	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = System.in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	        
	    public int[] nextIntArray(int n) {
	        return nextIntArray(n, 0);
	    }
	    
	    public int[] nextIntArray(int n, int off) {
	    	int[] arr = new int[n + off];
	    	for (int i = 0; i < n; i++) {
	    		arr[i + off] = nextInt();
	    	}
	    	return arr;
	    }
	    
	    public long[] nextLongArray(int n) {
	    	return nextLongArray(n, 0);
	    }
        
		public long[] nextLongArray(int n, int off) {
		    long[] arr = new long[n + off];
		    for (int i = 0; i < n; i++) {
		        arr[i + off] = nextLong();
		    }
		    return arr;
		}

	    private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}
}