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

public class AlmostArithmeticalProgressionSolver {

    private int n;

    private int[] b;

    public static void main(String[] args) {
        AlmostArithmeticalProgressionSolver solver = new AlmostArithmeticalProgressionSolver();

        solver.readData();
        int result = solver.solve();
        System.out.println(String.format("%d", result));
    }

    private void readData() {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }
    }

    private int solve() {
        if (n <= 2) {
            return n;
        }

        int result = 0;

        for (int i = 0; i < n - 1; i++) {
            Map<Integer, Pair> map = new HashMap<>(n);
            List<Pair> pairs = new ArrayList<>(n);
            int index = 0;

            for (int j = i + 1; j < n; j++) {
                if (b[j] == b[i]) {
                    index++;
                    continue;
                }

                Pair p = map.get(b[j]);
                if (p == null) {
                    p = new Pair(index, 1);
                    pairs.add(p);
                    map.put(b[j], p);
                }
                if (p.x < index) {
                    p.x = index;
                    p.y++;
                }
            }

            if (index + 1 > result) {
                result = index + 1;
            }

            for (Pair pair : pairs) {
                int iResult = 2 * pair.y + (pair.x == index ? 0 : 1);

                if (iResult > result) {
                    result = iResult;
                }
            }
        }

        return result;
    }

    public static class Pair {

        private int x;

        private int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
