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.Arrays;
import java.util.Scanner;


public class C {

    private final static boolean DEBUG = false;
    private static node[] a;
    
    /**
     * @param args
     */
    
    public static int solve(int i, int j, int n){
        
        
        int x = i;
        int y = j;
        if (a[x].pos > a[y].pos){
            int temp = x;
            x = y;
            y = temp;
        }
        
        int v1 = a[x].val;
        int v2 = a[y].val;
        
        
        int count = 0;
        do{
            count++;
            
            while (y < n-1 && a[y].pos < a[x].pos && a[y+1].val == v2)
                y++;
            if (a[y].val != v2) break;
            if (a[y].pos < a[x].pos) break; 
            count++;
            while (x < n-1 && a[x].pos < a[y].pos && a[x+1].val == v1)
                x++;
            if (a[x].val != v1) break;
            if (a[x].pos < a[y].pos) break; 
            
        }while (x < n);
        
        return count;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        a = new node[n];
        
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            a[i] = new node(x,i);
        }
        
        
        Arrays.sort(a);
        
        
        if (DEBUG)
            for(int i = 0; i < n; i++)
                System.out.println(a[i].val+" "+a[i].pos);
        
        int result = 1;
        
        for(int i = 0; i < n; i++){
            if (i == 0 || a[i].val != a[i-1].val){
                for (int j = i+1; j < n; j++)
                    if (a[j].val != a[i].val && a[j].val != a[j-1].val){
                        int count = solve(i,j,n);
                        result = Math.max(count, result);
                    }
            }
        }
        
        for(int i = 0; i < n; i++)
            if (i == 0 || a[i].val != a[i-1].val){
                int count = 0;
                int val = a[i].val;
                for(int j = i; j < n; j++){
                    if (a[j].val == val) count++;
                    else break;
                }
                result = Math.max(count,  result);
            }
        
        System.out.println(result);
        sc.close();

    }

}

class node implements Comparable<node>{
    public int val, pos;
    public node(int x, int y){
        val = x;
        pos = y;
    }
    
    public int compareTo( node E ) {
        if (E.val > val) return -1;
        if (E.val < val) return 1;
        if (E.val == val){
            if (E.pos > pos) return -1;
            if (E.pos < pos) return 1;
        }
        return 0;
    }
}
