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.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] A = new int[n];
        HashMap<Integer, Integer> H = new HashMap<Integer, Integer>();
        int index = 0;
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            if (!H.containsKey(x))
                H.put(x, index++);
            A[i] = H.get(x);
        }
        if (n < 3)
            System.out.println(n);
        else {
            int[][] next = new int[n][index];
            Arrays.fill(next[0], -1);
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < index; j++)
                    next[i][j] = next[i - 1][j];
                next[i][A[i - 1]] = i - 1;
            }
            int[][] DP = new int[n][n];
            int ans = 2;
            for (int i = 1; i < n; i++)
                for (int j = 0; j < i; j++) {
                    if (next[j][A[i]] == -1)
                        DP[j][i] = 2;
                    else
                        DP[j][i] = 1 + DP[next[j][A[i]]][j];
                    ans = Math.max(ans, DP[j][i]);
                }
            System.out.println(ans);
        }
    }
}
