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.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().run(in, out);
        out.close();
    }

    void run(FastScanner in, PrintWriter out) {

        int N = in.nextInt();
        int[] a = new int[N];

        int numUnique = 0;
        HashMap<Integer, Integer> ids = new HashMap<>();
        for (int i = 0; i < N; i++) {
            a[i] = in.nextInt();
            if (!ids.containsKey(a[i])) ids.put(a[i], numUnique++);
        }

        int[][] dp = new int[numUnique][numUnique];
        int max = 0;

        for (int i = 0; i < N; i++) {
            // pattern ending at i
            boolean zeroDeltaAdded = false;
            for (int j = 0; j < i; j++) {
                int iId = ids.get(a[i]);
                int jId = ids.get(a[j]);
                if (iId == jId) {
                    if (!zeroDeltaAdded) {
                        dp[iId][iId]++;
                        zeroDeltaAdded = true;
                    }
                } else {
                    dp[jId][iId] = dp[iId][jId]+1;
                }
                max = Math.max(max, dp[jId][iId]);
            }
        }
        out.println(max+1);
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }

        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());
        }
    }
}
