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

public class C255 {



    void solve(){
        int n = readInt();
        int[] a = new int[n];

        for(int i = 0;i<n;i++){
            a[i] = readInt();
        }


        List<Integer>[] b = new List[1_000_000 + 1];
        boolean[] used = new boolean[b.length];
        List<Integer> exist = new ArrayList<>();
        int ans = 0;

        for(int i = 0;i<n;i++){
            if(!used[a[i]]){
                exist.add(a[i]);
                b[a[i]] = new ArrayList<>();
            }
            used[a[i]] = true;
            b[a[i]].add(i);
        }

        for(int i = 0;i<exist.size();i++){
            int one = exist.get(i);
            ans = Math.max(ans, b[one].size());
            for(int j = 0;j<exist.size();j++){
                if(i == j) continue;
                int x = 1;
                int last = b[one].get(0);
                int y = 0;
                int two = exist.get(j);
                int res = 1;
                boolean right = true;
                while(true){
                    if(right){
                        while(y < b[two].size() && b[two].get(y) < last) y++;
                        if(y == b[two].size()) break;
                        last = b[two].get(y);
                    }else{
                        while(x < b[one].size() && b[one].get(x) < last) x++;
                        if(x == b[one].size()) break;
                        last = b[one].get(x);
                    }
                    res++;
                    right = !right;
                }
                ans = Math.max(ans, res);
            }
        }

        out.print(ans);
    }

    public static void main(String[] args) {
        new C255().run();
    }

    void run(){
        init();
        solve();
        out.close();
    }

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok = new StringTokenizer("");

    void init(){
        in = new BufferedReader(new InputStreamReader(System.in));
        out  = new PrintWriter(System.out);
    }

    String readLine(){
        try{
            return in.readLine();
        }catch(Exception ex){
            throw new RuntimeException(ex);
        }
    }
    String readString(){
        while(!tok.hasMoreTokens()){
            String nextLine = readLine();
            if(nextLine == null) return null;
            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt(){
        return Integer.parseInt(readString());
    }

    long readLong(){
        return Long.parseLong(readString());
    }

    double readDouble(){
        return Double.parseDouble(readString());
    }
}
