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.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import static java.lang.Math.*;
@SuppressWarnings("unused")

public class round156C {
    static BufferedReader br = new BufferedReader(new InputStreamReader(
            System.in));
    static StringTokenizer st = new StringTokenizer("");

    static int nextInt() throws Exception {
        return Integer.parseInt(next());
    }

    static String next() throws Exception {
        while (true) {
            if (st.hasMoreTokens()) {
                return st.nextToken();
            }
            String s = br.readLine();
            if (s == null) {
                return null;
            }
            st = new StringTokenizer(s);
        }
    }

    public static void main(String[] args)throws Exception {
        int n = nextInt();
        int [] seq = new int [n];
        for(int i = 0 ; i < n ; ++i)
            seq[i] = nextInt();
        if(n < 3){
            System.out.println(n);
        }else{
            int max = -1;
            for(int i = 0 ; i < n ; ++i){//start at each index          
                int [] occ = new int [n];
                Arrays.fill(occ, -1);
                int cnt = 0;
                for(int j = i ; j < n ; ++j){
                    if(seq[i] == seq[j]){
                        occ[cnt++] = j;
                    }
                }                               
                max = max(cnt, max);
                HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
                for(int j = 0 ; j < cnt - 1 ; ++j){
                    HashSet<Integer> taken = new HashSet<Integer>();
                    for(int k = occ[j] + 1 ; k < occ[j + 1] ; ++k){
                        if(taken.contains(seq[k]))
                            continue;
                        taken.add(seq[k]);
                        Integer x = count.get(seq[k]);
                        if(x == null)
                            count.put(seq[k], 1);
                        else
                            count.put(seq[k], x + 1);
                    }
                }
                HashSet<Integer> after = new HashSet<Integer>();            
                for(int j = occ[cnt - 1] + 1 ; j < n ; ++j)
                    after.add(seq[j]);
                int mx = 0;
                int mx_num = -1;
                for(Entry<Integer, Integer> e : count.entrySet()){              
                    if(e.getValue() > mx){
                        mx = e.getValue();
                        mx_num = e.getKey();
                    }else{
                        if(e.getValue() == mx){                         
                            if(after.contains(e.getKey())){
                                mx_num = e.getKey();
                            }
                        }
                    }
                }
                boolean addOne = false;
                for(int j = occ[cnt - 1] + 1; j < n ; ++j)
                    if(seq[j] == mx_num){
                        addOne = true;
                        break;
                    }
                int tmp = mx * 2 + 1;
                tmp += addOne == true ? 1 : 0;
                max = max(max, tmp);
            }
            System.out.println(max == 1 ? 2 : max);
        }
        
        
    }
}
