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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class D385 {

    public static class Pair {
        int a;
        int b;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            if (a != pair.a) return false;
            return b == pair.b;

        }

        @Override
        public int hashCode() {
            int result = a;
            result = 31 * result + b;
            return result;
        }

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) {

        MyScanner in = new MyScanner();
        int n = in.nextInt();
        int[] a = new int[n];

        for(int i=0;i<n;++i){
            a[i] = in.nextInt();
        }

        Map<Long, Integer> map = new HashMap<>();

        Map<Integer, Integer> cnt = new HashMap();

        Set<Integer> visited = new HashSet<>();

        for(int i=0;i<n;++i) {
            cnt.put(a[i], cnt.getOrDefault(a[i], 0) + 1);
        }

        int max = 1;
        if(cnt.size()>1){
            max = 2;
        }

        for(int i=0;i<n;++i){
            if(cnt.get(a[i])==1){
                continue;
            }
            if(cnt.get(a[i]) == 2 && i>0 && a[i-1]!=a[i]){
                max = 3;
            }
            visited.clear();
            for(int j=i-1;j>=0;--j){
                if(a[i]!=a[j] && !visited.contains(a[j])) {
                    long prev = 1L*a[i] * 1_000_000 + a[j];
                    long curr = 1L*a[j] * 1_000_000 + a[i];
                    int currMax = map.getOrDefault(curr, 1);
                    map.put(curr, Math.max(currMax, map.getOrDefault(prev, 0) + 1));
                    visited.add(a[j]);
                }
            }
        }


        for(Integer val :map.values()){
            max = Math.max(max, val + 1);
        }

        for(Integer val :cnt.values()){
            max = Math.max(max, val);
        }
        System.out.println(max);

    }

    // -----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    // --------------------------------------------------------

}