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

// Created by @thesupremeone on 30/06/21
public class AlmostAP {
    void solve() throws IOException {
        int n = getInt();
        int[] a = new int[n];
        HashMap<Integer, TreeSet<Integer>> map = new HashMap<>();
        ArrayList<Integer> distinct = new ArrayList<>();
        for (int i = 0; i < n; i++){
            int ai = getInt();
            a[i] = ai;
            TreeSet<Integer> set;
            if(map.containsKey(ai)){
                set = map.get(ai);
            }else {
                set = new TreeSet<>();
                distinct.add(ai);
                map.put(ai, set);
            }
            set.add(i);
        }
        int ans = 0;
        for(int i=0; i<distinct.size(); i++){
            int first = distinct.get(i);
            for (int j=i; j<distinct.size(); j++){
                int second = distinct.get(j);
                int k = -1;
                int count = 0;
                boolean findFirst = true;
                while (k<n){
                    Integer next;
                    TreeSet<Integer> set;
                    if(findFirst){
                        set = map.get(first);
                    }else {
                        set = map.get(second);
                    }
                    next = set.higher(k);
                    if(next==null){
                        break;
                    }
                    k = next;
                    count++;
                    findFirst = !findFirst;
                }
                ans = Math.max(count, ans);
            }
        }
        println(ans);
    }

    public static void main(String[] args) throws Exception {
        if (isOnlineJudge()) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new BufferedWriter(new OutputStreamWriter(System.out));
            new AlmostAP().solve();
            out.flush();
        } else {
            localJudge = new Thread();
            in = new BufferedReader(new FileReader("input.txt"));
            out = new BufferedWriter(new FileWriter("output.txt"));
            localJudge.start();
            new AlmostAP().solve();
            out.flush();
            localJudge.suspend();
        }
    }
    static boolean isOnlineJudge(){
        try {
            return System.getProperty("ONLINE_JUDGE")!=null
                    || System.getProperty("LOCAL")==null;
        }catch (Exception e){
            return true;
        }
    }
    // Fast Input & Output
    static Thread localJudge = null;
    static BufferedReader in;
    static StringTokenizer st;
    static BufferedWriter out;
    static String getLine() throws IOException{
        return in.readLine();
    }
    static String getToken() throws IOException{
        if(st==null || !st.hasMoreTokens())
            st = new StringTokenizer(getLine());
        return st.nextToken();
    }
    static int getInt() throws IOException {
        return Integer.parseInt(getToken());
    }
    static long getLong() throws IOException {
        return Long.parseLong(getToken());
    }
    static void print(Object s) throws IOException{
        out.write(String.valueOf(s));
    }
    static void println(Object s) throws IOException{
        out.write(String.valueOf(s));
        out.newLine();
    }
}