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.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Sheng Cao
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        AlmostArithmeticalProgression solver = new AlmostArithmeticalProgression();
        solver.solve(1, in, out);
        out.close();
    }
}

class AlmostArithmeticalProgression {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n1 = in.nextInt();
        int[] l1 = new int[n1];
        for (int i = 0; i < n1; i++) {
            l1[i] = in.nextInt();
        }
        int[] vals = ArrayUtil.sortUnique(l1);
        for (int i = 0; i < l1.length; i++) {
            l1[i] = Arrays.binarySearch(vals, l1[i]);
        }

        int[][] dp = new int[vals.length][vals.length];
        for (int i = 0; i < n1; i++) {
            int cur = l1[i];
            for (int from = 0; from < vals.length; from++) {
                int temp = dp[cur][from] + 1;
                dp[from][cur] = temp;
            }
        }
        int ans = 1;
        for (int[] e : dp) for (int f : e) if (f > ans) { ans = f; }
        out.writeLine(ans);
    }
}

class InputReader {
    public BufferedReader in = null;
    public StringTokenizer st = null;

    public InputReader(InputStream usingStream) {
        in = new BufferedReader(new InputStreamReader(usingStream));

    }
    public String next(){
        for (;st == null || !st.hasMoreTokens();){
            String currentLine = null;
            try {
                currentLine = in.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (currentLine == null) return null;
            st = new StringTokenizer(currentLine);
        }
        return st.nextToken();
    }
    public int nextInt(){
        return Integer.parseInt(next());
    }

}

class OutputWriter {
    private PrintWriter usingPrintWriter = null;

    public OutputWriter(OutputStream usingStream){
        usingPrintWriter = new PrintWriter(usingStream);
    }
    public OutputWriter(Writer usingWriter){
        usingPrintWriter = new PrintWriter(usingWriter);
    }
    public void writeLine(Object ... l1){
        for (int i = 0;i < l1.length; i++){
            if (i != 0) usingPrintWriter.print(" ");
            usingPrintWriter.print(l1[i]);
        }
        usingPrintWriter.println();
    }
    public void flush(){
        usingPrintWriter.flush();
    }
    public void close(){
        flush();
        usingPrintWriter.close();
    }
}

class ArrayUtil {
    public static int[] sortUnique(int[] l1) {
        int[] copy = l1.clone();
        Arrays.sort(copy);
        int size = 0;
        for (int i = 0; i < copy.length; i++) {
            if (i == 0 || copy[i] != copy[i - 1]) {
                copy[size++] = copy[i];
            }
        }
        return Arrays.copyOf(copy, size);
    }

}
