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

public class AlmostArithmeticalProgression 
{

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		int[][] dp = new int[4000][4000];
		boolean[] started = new boolean[4000];
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int logged = 0;
		
		int n = sc.nextInt();
		int r = 0;
		
		for(int i = 0; i < n; i++)
		{
			int cur = sc.nextInt();
//			System.out.println("-");
			
			if(!map.containsKey(cur))
			{
				map.put(cur, logged);
				logged++;
			}
			
			int vid = map.get(cur);
			
			started[vid] = true;
			
			for(int j = 0; j < logged; j++)
			{
				boolean up = false;
				if(started[j] && (dp[j][vid]%2 == 1 || dp[j][vid] == 0))
				{
					up = true;
					if(dp[j][vid] == 0 && j != vid)dp[j][vid]++;
					dp[j][vid]++;
//					System.out.println(j + " " + vid + ": " + dp[j][vid]);
					r = Math.max(r, dp[j][vid]);
				}
				if((dp[vid][j]%2 == 0) && (vid != j || !up))
				{
					dp[vid][j]++;
//					System.out.println("! " + vid + " " + j + ": " + dp[vid][j]);
					r = Math.max(r, dp[vid][j]);
				}
			}
		}
		
//		System.out.println(dp[0][1]);
		System.out.println(r);
	}

}
