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.*;
import java.io.*;
import java.math.*;

public class Main {

	static class FastScanner {
		BufferedReader s;
		StringTokenizer st;

		public FastScanner(InputStream InputStream) {
			st = new StringTokenizer("");
			s = new BufferedReader(new InputStreamReader(InputStream));
		}

		public FastScanner(File f) throws FileNotFoundException {
			st = new StringTokenizer("");
			s = new BufferedReader(new FileReader(f));
		}

		public int nextInt() throws IOException {
			if (st.hasMoreTokens())
				return Integer.parseInt(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextInt();
			}
		}

		public BigInteger big() throws IOException {
			if (st.hasMoreTokens())
				return new BigInteger(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return big();
			}
		}

		public double nextDouble() throws IOException {
			if (st.hasMoreTokens())
				return Double.parseDouble(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextDouble();
			}
		}

		public long nextLong() throws IOException {
			if (st.hasMoreTokens())
				return Long.parseLong(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextLong();
			}
		}

		public String next() throws IOException {
			if (st.hasMoreTokens())
				return st.nextToken();
			else {
				st = new StringTokenizer(s.readLine());
				return next();
			}

		}

		public String nextLine() throws IOException {
			return s.readLine();
		}

		public void close() throws IOException {
			s.close();
		}

	}

	public static void main(String[] args) throws java.lang.Exception {
		FastScanner in = new FastScanner(System.in);
		int n = in.nextInt();
	    int[] arr = new int[n + 2];
	    for(int x = 1; x <= n; x++) 
	    	arr[x] = in.nextInt();
	    int dp[][] = new int[n + 2][n + 2];
	    int ans=0;
	    for(int i=1;i<=n;i++){
	        for(int j=0,x=0;j<i;j++){
	            dp[j][i]=dp[x][j]+1;
	            if(arr[j]==arr[i]) 
	            x=j;
	            ans=Math.max(ans,dp[j][i]);
	        }
	    }
	    System.out.println(ans);
	}
}
/*
 * #include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int x;
    cin>>n;
    vector<int> arr(n+2);
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    
    int DP[n+2][n+2];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            DP[i][j]=0;
        }
    }
    

    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0,x=0;j<i;j++){
            DP[j][i]=DP[x][j]+1;
            if(arr[j]==arr[i]) 
            x=j;
            ans=max(ans,DP[j][i]);
        }
    }

    cout<<ans<<"\n";
}

 */
