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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * Created by mostafa on 9/12/17.
 */
public class AlmostArithProg {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner();
        int n = sc.nextInt();
        int[] b = new int[n];

        TreeMap<Integer, Integer> compress = new TreeMap<>();
        int cur = 0;
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if(!compress.containsKey(x))
                compress.put(x, cur++);
            b[i] = compress.get(x);
        }

        if(n == 1) {
            System.out.println(1);
            return;
        }
        int[][] last = new int[n][n];
        for(int i = 0; i < n; i++)
            Arrays.fill(last[i], -1);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++)
                last[i][b[j]] = j;
        }

        int[][] dp = new int[n][n];
        int max = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < i; j++) {
                int l = last[j][b[i]];
                if(l == -1)
                    dp[i][j] = 2;
                else
                    dp[i][j] = 1 + dp[j][l];
                max = Math.max(max, dp[i][j]);
            }

        System.out.println(max);
    }

    static class Scanner {
        BufferedReader br; StringTokenizer st;
        Scanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while(st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        boolean ready() throws IOException {
            return br.ready();
        }

    }

}
