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.awt.Container;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.concurrent.LinkedBlockingDeque;

import javax.swing.border.Border;

public class a {

	public static long mod = (long) Math.pow(10, 9) + 7;

	private static class node implements Comparable<node> {
		String ans;

		node(String an) {
			ans = an;
		}

		@Override
		public int compareTo(node o) {
			if (o.ans.length() > ans.length())
				return -1;
			while (o.ans.length() < ans.length())
				return 1;
			for (int i = 0; i < o.ans.length(); i++) {
				if (o.ans.charAt(i) > ans.charAt(i))
					return -1;
				else if (o.ans.charAt(i) < ans.charAt(i))
					return 1;
			}

			return 1;

		}

	}

	public static class point {
		int screen;
		int order;

		point(int x, int y) {
			screen = x;
			order = y;

		}

	}

	public static int ch(long y) {
		int r = Long.bitCount(y);
		return r;
	}

	public static long gcd(long x, long y) {
		if (y == 0)
			return x;

		return gcd(y, x % y);
	}

	public static boolean ch[] = new boolean[10000005];
	public static ArrayList<Integer> prime = new ArrayList();

	// public static Queue<Integer> pp;

	public static void sieve(int k) {
		ch[0] = ch[1] = true;

		for (int i = 2; i <= k; i++) {
			if (!ch[i]) {
				prime.add(i);
				// pp.add(i);
				for (long j = (long) i * (long) i; j <= k; j += i) {
					ch[(int) j] = true;
				}
			}
		}

	}

	public static long pw(int x, int power, int mod) {
		if (power == 1)
			return x % mod;
		else if (power % 2 == 0)
			return pw((x % mod * x % mod) % mod, power / 2, mod);
		else
			return (pw(x, power - 1, mod) % mod * x % mod) % mod;

	}

	public static String addToString(String a, int index, char b) {
		String ans = "";
		for (int i = 0; i < a.length(); i++) {
			if (i == index) {
				ans += b;
				index = -1;
				i--;
				continue;
			}
			ans += a.charAt(i);
		}
		return ans;
	}

	public static int bit[];

	public static void add(int idx, int cost) {
		while (idx < bit.length) {
			bit[idx] += cost;
			idx += (idx & -idx);
		}

	}

	public static int get(int idx) {
		int res = 0;
		while (idx > 0) {
			res += bit[idx];
			idx -= (idx & -idx);
		}
		return res;
	}

	public static int dx[] = { 0, 1, 0, -1 };
	public static int dy[] = { 1, 0, -1, 0 };

	public static ArrayList<Integer> solve(ArrayList<Integer> coff,
			ArrayList<Integer> power) {
		ArrayList<Integer> ans = new ArrayList();
		for (int x = -100; x < 101; x++) {
			long t = 0;
			for (int j = 0; j < coff.size(); j++) {
				t += coff.get(j) * Math.pow(x, power.get(j));
			}
			if (t == 0)
				ans.add(x);
		}
		return ans;
	}

	public static int dp[][];
	public static int n;
	public static int a[];
	public static int next[];

	public static int solve(int one, int two) {
		if (two == -1||one==-1)
			return 0;
			if (dp[one][two] != -1)
				return dp[one][two];

		
			if(next[one]>two)
			return dp[one][two] = solve(two, next[one]) + 1;
			else return dp[one][two] = solve(next[one], two);
				
		

	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader in = new BufferedReader(new FileReader(
		// "corporate_gifting.txt"));
		StringBuilder qq = new StringBuilder();
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		// PrintWriter out = new PrintWriter(new FileWriter("out.txt"));
		// System.out.println('a' - 'A');

		n = Integer.parseInt(in.readLine());
		String y[] = in.readLine().split(" ");
		a = new int[n];
		dp = new int[n][n];
		next = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(y[i]);
			Arrays.fill(dp[i], -1);
		}

		int pos[] = new int[1000005];
		int c[] = new int[1000005];
		Arrays.fill(pos, -1);
		int max = 0;
		for (int i = n - 1; i >= 0; i--) {
			next[i] = pos[a[i]];
			pos[a[i]] = i;
			 c[a[i]]++;
			max = Math.max(max, c[a[i]]);
		}
		if (n == 1)
			out.println(1);
		else {

			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					max = Math.max(max, solve(i, j) + 2);
				}
			}
			out.println(max);
		}
		out.close();

	}
}