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.List;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;

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

class TaskA {
    public void solve(int testNumber, InputReader jin, PrintWriter jout) {
        int n = jin.int32();

        int count = 0;
        int[] index = new int[(int)1e6 + 1];
        Arrays.fill(index, -1);

        int maxLength = 0;

        List<List<Integer>> nlst = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int x = jin.int32();
            if(index[x] == -1) {
                List<Integer> tlst = new ArrayList<>();
                index[x] = count++;
                nlst.add(tlst);
            }
            List<Integer> clst = nlst.get(index[x]);
            clst.add(i);
            maxLength = Math.max(maxLength, clst.size());
        }

        for(int i = 0; i < count; i++) {
            List<Integer> alst = nlst.get(i);
            for(int j = i + 1; j < count; j++) {
                List<Integer> jlst = nlst.get(j);
                if(alst.size() + jlst.size() < maxLength)
                    continue;
                int mLstCnt = mergeLists(alst, jlst);
                maxLength = Math.max(maxLength, mLstCnt);
            }
        }

        jout.println(maxLength);
    }

    private int mergeLists(List<Integer> aLst, List<Integer> bLst) {
        int aInd = 0, aLen = aLst.size();
        int bInd = 0, bLen = bLst.size();

        int solution = 0;
        boolean aTurn = aLst.get(aInd) < bLst.get(bInd);
        while(aInd < aLen && bInd < bLen) {
            int aNext = aLst.get(aInd);
            int bNext = bLst.get(bInd);
            if(aTurn) {
                if(bNext < aNext) {
                    bInd++;
                } else {
                    solution++;
                    aTurn = !aTurn;
                    aInd++;
                }
            } else {
                if(aNext < bNext) {
                    aInd++;
                } else {
                    solution++;
                    aTurn = !aTurn;
                    bInd++;
                }
            }
        }

        if(aInd < aLen && aTurn) {
            solution++;
        }
        
        if(bInd < bLen && !aTurn) {
            solution++;
        }

        return solution;
    }
}

class InputReader {
    private static final int bufferMaxLength = 1024;
    private InputStream in;
    private byte[] buffer;
    private int currentBufferSize;
    private int currentBufferTop;
    private static final String tokenizers = " \t\r\f\n";

    public InputReader(InputStream stream) {
        this.in = stream;
        buffer = new byte[bufferMaxLength];
        currentBufferSize = 0;
        currentBufferTop = 0;
    }

    private boolean refill() {
        try {
            this.currentBufferSize = this.in.read(this.buffer);
            this.currentBufferTop = 0;
        } catch(Exception e) {}
        return this.currentBufferSize > 0;
    }

    public String line() {
        StringBuffer tok = new StringBuffer();
        Byte first;
        while((first = readChar()) != null) {
            tok.append((char)first.byteValue());
            if((char)first.byteValue() == '\n')
                break;
        }
        return tok.toString();
    }

    public Byte readChar() {
        if(currentBufferTop < currentBufferSize) {
            return this.buffer[this.currentBufferTop++];
        } else {
            if(!this.refill()) {
                return null;
            } else {
                return readChar();
            }
        }
    }

    public String token()  {
        StringBuffer tok = new StringBuffer();
        Byte first;
        while((first = readChar()) != null && (tokenizers.indexOf((char) first.byteValue()) != -1));
        if(first == null) return null;
        tok.append((char)first.byteValue());
        while((first = readChar()) != null && (tokenizers.indexOf((char) first.byteValue()) == -1)) {
            tok.append((char)first.byteValue());
        }
        return tok.toString();
    }


    public String next() {
        return token();
    }

    public Integer int32() throws NumberFormatException {
        String tok = token();
        return tok == null? null : Integer.parseInt(tok);
    }

    public Long int64() throws NumberFormatException {
        String tok = token();
        return tok == null? null : Long.parseLong(tok);
    }
}

