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.*;

public class C {
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int n = fs.nextInt(), MAX = 1000010, pos = 0;
        int[] a = fs.nextIntArray(n);
        int[] map = new int[MAX];
        Arrays.fill(map, -1);
        for(int i = 0; i < n; i++) {
            if(map[a[i]] == -1) map[a[i]] = pos++;
        }



        int res = 1;

        int[][] back = new int[pos][pos];
        for(int[] abc : back) Arrays.fill(abc, -1);
        int[][] len  = new int[pos][pos];

        for(int i = 0; i < n; i++) {
            boolean[] seen = new boolean[pos];

            for(int j = i+1; j < n; j++) {

               int pi = map[a[i]];
               int pj = map[a[j]];

               if(seen[pj]) continue;
               seen[pj] = true;

               if(i > back[pi][pj]) {
                   len[pi][pj] = len[pj][pi] + 1;
                   back[pi][pj] = j-1;
               }

            }

        }

        for(int i = 0; i < pos; i++) {
            for(int j = 0; j < pos; j++) {
                res = Math.max(res, len[i][j] + 1);
            }
        }

        out.println(res);

        out.close();
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            try	{
                br = new BufferedReader(new InputStreamReader(System.in));
                //                br = new BufferedReader(new FileReader("testdata.out"));
                st = new StringTokenizer("");
            } catch (Exception e){e.printStackTrace();}
        }

        public String next() {
            if (st.hasMoreTokens())	return st.nextToken();
            try {st = new StringTokenizer(br.readLine());}
            catch (Exception e) {e.printStackTrace();}
            return st.nextToken();
        }

        public int nextInt() {return Integer.parseInt(next());}

        public long nextLong() {return Long.parseLong(next());}

        public double nextDouble() {return Double.parseDouble(next());}

        public String nextLine() {
            String line = "";
            try {line = br.readLine();}
            catch (Exception e) {e.printStackTrace();}
            return line;
        }

        public Integer[] nextIntegerArray(int n) {
            Integer[] a = new Integer[n];
            for(int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        public char[] nextCharArray() {
            return nextLine().toCharArray();
        }
    }

}