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

public class C2 {

    static Map<Point, Integer> map = new HashMap<Point, Integer>();
    static Point end;

    public static void main(String[] Args) {

        int w = si();
        int[] a = new int[w + 1];
        for (int i = 1; i <= w; i++) {
            a[i] = si();
        }
        int[][] dp = new int[4001][4001];

        int x = 1;
        for (int i = 1; i <= w; i++) {

            for (int j = 0, p = 0; j < i; j++) {

                dp[i][j] = dp[j][p] + 1;

                if (a[i] == a[j])
                    p = j;
                x = Math.max(x, dp[i][j]);
            }
        }

        System.out.println(x);
    }

    static int toi(Object s) {
        return Integer.parseInt(s.toString());
    }

    // ----------------------- Library ------------------------
    static int[] dx = { 1, 0, -1, 1, -1, 1, 0, -1 }, dy = { 1, 1, 1, 0, 0, -1,
            -1, -1 };
    static Scanner scan = new Scanner(System.in);
    static int INF = 2147483647;

    // finds GCD of a and b using Euclidian algorithm
    public int GCD(int a, int b) {
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }

    static List<String> toList(String[] a) {
        return Arrays.asList(a);
    }

    static String[] toArray(List<String> a) {
        String[] o = new String[a.size()];
        a.toArray(o);
        return o;
    }

    static int[] pair(int... a) {
        return a;
    }

    static int si() {
        return scan.nextInt();
    }

    static String ss() {
        return scan.next();
    }

    static int[] sai(int n) {
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++)
            a[i] = si();

        return a;
    }

    static int[] sai_(int n) {
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = si();

        return a;
    }

    static String[] sas(int n) {
        String[] a = new String[n];
        for (int i = 0; i < a.length; i++)
            a[i] = ss();
        return a;
    }

    static Object[][] _sm1(int r, int c) {
        Object[][] a = new Object[r][c];
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                a[i][j] = scan.next();
        return a;
    }

    static Object[][] _sm2(int r) {
        Object[][] a = new Object[r][3];
        for (int i = 0; i < r; i++)
            a[i] = new Object[] { ss(), ss(), ss() };
        return a;
    }
}