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 Main {

    static FastReader in = new FastReader("in.txt");
    static PrintWriter out = new PrintWriter(System.out);

    static final int N = 4040;
    
    static int n, a[];
    static ArrayList<ArrayList<Integer>> p = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        n = in.nextInt();
        a = new int[n];

        for(int i = 0; i < n; ++i)
            a[i] = in.nextInt();

        compress();
        for(int i = 0; i < N; ++i)
            p.add(new ArrayList<>());

        for(int i = 0; i < n; ++i)
            p.get(a[i]).add(i);

        int ans = 0;
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                if(i == j)
                    ans = Math.max(ans, p.get(i).size());
                else
                    ans = Math.max(ans, len(i, j));
            }
        }

        out.println(ans);
        out.flush();
    }

    static int len(int x, int y){

        int cnt = 0, prev = -1, parity = 1, i = 0, j = 0, xl = p.get(x).size(), yl = p.get(y).size();

        while(i < xl && j < yl) {
            if(p.get(x).get(i) < p.get(y).get(j)){
                if(parity == 1) { ++cnt; parity = 0; }
                ++i;
            } else {
                if(parity == 0) { ++cnt; parity = 1; }
                ++j;
            }
        }

        if(i < xl && parity == 1) ++cnt;
        if(j < yl && parity == 0) ++cnt;

        return cnt;
    }

    static void compress(){
        int[] t0 = Arrays.copyOf(a, n);
        Arrays.sort(t0);

        for(int i = 0; i < n; ++i){
            int idx = Arrays.binarySearch(t0, a[i]);
            a[i] = idx;
        }
    }

    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader(String file) {
            try {
                br = new BufferedReader(new FileReader(file));
            } catch (FileNotFoundException e) {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }

        String next() {

            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) { e.printStackTrace(); }
            }

            return st.nextToken();
        }

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

        long nextLong() { return Long.parseLong(next()); }

        double nextDouble() { return Double.parseDouble(next()); }

        String nextLine() {

            String str = "";

            try {
                str = br.readLine();
            } catch (IOException e) { e.printStackTrace(); }

            return str;
        }
    }
}