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.
/**
 * Alipay.com Inc. Copyright (c) 2004-2020 All Rights Reserved.
 */

import java.util.*;

/**
 *
 * @author linwanying
 * @version $Id: C255.java, v 0.1 2020年03月29日 4:46 PM linwanying Exp $
 */
public class C255 {
    public static void main(String[] args) {
        new C255().run();
    }

    public void run() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        if (n <= 2) {
            System.out.println(n);
            return;
        }

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

        Map<Integer, Integer> map = new HashMap<>();
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], idx++);
            }
        }

        int[][] dp = new int[n][map.size()];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < map.size(); ++j) {
                dp[i][j] = 1;
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i][map.get(arr[j])] = Math.max(dp[j][map.get(arr[i])] + 1, dp[i][map.get(arr[j])]);
            }
        }

        int result = 2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < map.size(); ++j) {
                result = Math.max(result, dp[i][j]);
            }
        }

        System.out.println(result);

    }
}