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.*;
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;

public class Main {

    
    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                                            //(new FileReader("input.in"));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        //PrintWriter pw = new PrintWriter("output.out", "UTF-8");
     
        int n = parseInt(in.readLine());
        int [] arr = new int[n+1];
        tk = new StringTokenizer(in.readLine());
        for(int i=1; i<=n; i++)
            arr[i] = parseInt(tk.nextToken());
        
        int [][] dp = new int[n+1][n+1];
        for(int i=0; i<=n; i++)
            dp[i][0] = 1;
        
        int ans = 1;
        for(int a=1; a<=n; a++) {
            for(int b=1,c=0; b<a; b++) {
                dp[a][b] = dp[b][c]+1;
                if(arr[a]==arr[b]) {
                    c = b;
                   // continue;
                }
                ans = max(ans,dp[a][b]);
            }
        }
        
        System.out.println(ans);
    }
    
}