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.Arrays;
import java.util.List;
import java.util.Locale;
import java.util.Scanner;

public class CodeForces
{
    public void solve() throws IOException
    {
        initIO();


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

        int f[][]=new int[n][n];
        for (int i = 0; i < f.length; i++)
            Arrays.fill(f[i],Integer.MAX_VALUE);

        for (int i = n-1; i >=0 ; i--)
            for (int j=n-1;j>i;j--)
                if (a[i]==a[j])
                    f[i][j]=j;
                else
                    f[i][j]=j+1==n?Integer.MAX_VALUE:f[i][j+1];

        int dp[][]=new int[n][n];
        int res=1;
        for (int i = n-1; i >=0 ; i--)
            for (int j=n-1;j>i;j--)
            {
                dp[i][j]=2;
                if (j+1<n && f[i][j+1]!=Integer.MAX_VALUE)
                    dp[i][j]=Math.max(dp[i][j],1+dp[j][f[i][j+1]]);
                res=Math.max(res,dp[i][j]);
            }

        out.println(res);
        out.flush();
        out.close();
    }





    static Scanner in;
    static FastReader fin;
    static FastWriter out;

    CodeForces() throws IOException
    {
        solve();
    }

    public static void main(String[] args) throws IOException
    {
        new CodeForces();
    }

    void initIO() throws IOException
    {
        if (System.getProperty("ONLINE_JUDGE") == null)
        {
            fin = new FastReader(new InputStreamReader(new FileInputStream("input.txt")));
            in = new Scanner(new File("input.txt"));
        }
        else
        {
            fin=new FastReader(new InputStreamReader(System.in));
            in=new Scanner(System.in);
        }
        out = new FastWriter(new OutputStreamWriter(System.out));
    }

    static class Algorithms
    {
        public static <T extends Comparable<T>> int max(T []a)
        {
            int max=0;
            for (int i = 1; i <a.length ; i++)
            {
                if (a[i].compareTo(a[max])>0)
                    max=i;
            }
            return max;
        }

    }
    static class Figure
    {
        static double squareTriangle(Point<Double,Double> A, Point<Double,Double> B, Point <Double,Double>C)
        {
            double a=Point.length(A,B),b=Point.length(A,C),c=Point.length(B,C);
            double p=(a+b+c)/2;
            return Math.sqrt(p*(p-a)*(p-b)*(p-c));
        }
    }
    static class Line
    {
        double K, B;
        static final int OX = 0, OY = 1, GENERAL = 2;
        int kind;

        Line(Point<Double, Double> a, Point<Double, Double> b)
        {
            if (equals(a.x, b.x))
            {
                K = 0;
                kind = OY;
                this.B = a.x;
            }
            else
            {
                if (equals(a.y, b.y))
                {
                    K = 0;
                    kind = OX;
                    B = a.y;
                }
                else
                {
                    kind = GENERAL;
                    K = (b.y - a.y)/(b.x - a.x) ;
                    B = a.y - K * a.x;
                }
            }
        }

        static Point<Double, Double> intersec(Line a, Line b)
        {
            switch (a.kind)
            {
                case OX:
                    if (b.kind == OX)
                        return null;
                    else
                    if (b.kind == OY)
                        return new Point<Double, Double>(b.B, a.B);
                    else
                        return new Point<Double, Double>((a.B-b.B)/b.K,a.B);
                case OY:
                    if (b.kind== OX)
                        return new Point<Double, Double>(a.B,b.B);
                    else
                    if (b.kind==OY)
                        return null;
                    else
                        return new Point<Double, Double>(a.B,b.K*a.B+b.B);
                case GENERAL:
                    if (b.kind==GENERAL)
                    {
                        double x=(b.B-a.B)/(a.K-b.K),y=a.K*x+a.B;
                        return new Point<Double, Double>(x,y);
                    }
                    else return intersec(b,a);
                default: return null;
            }
        }
        static boolean equals(double a, double b)
        {
            if (Math.abs(a - b) < 0.00001)
                return true;
            else return false;
        }

    }

    static class Point<T1, T2> implements Comparable<Point>
    {
        T1 x;
        T2 y;
        public String toString()
        {
            return x+"        "+y;
        }
        public Point(T1 first, T2 second)
        {
            x = first;
            y = second;
        }

        public int compareTo(Point p)
        {
            return 1;
        }

        static double length(Point<Double, Double> a, Point<Double, Double> b)
        {
            return Math.sqrt(Math.pow(a.x - b.x, 2.) + Math.pow(a.y - b.y, 2.));
        }

        static Point<Double, Double> center(Point<Double, Double> a, Point<Double, Double> b)
        {
            return new Point<Double, Double>((a.x + b.x) / 2, (a.y + b.y) / 2);
        }
    }

    static class FastWriter extends PrintWriter
    {
        public FastWriter(Writer out)
        {
            super(out);
        }

        public void printList(List l)
        {
            print(l.get(0));
            for (int i = 1; i < l.size(); i++)
            {
                print(" ");
                print(l.get(i));
            }
            println();
        }

        public void printDouble(double d, int accuracy)
        {
            printf("%." + accuracy + "f", d);
        }
    }

    static class FastReader
    {
        StreamTokenizer in;

        public FastReader(InputStreamReader inputStream) throws IOException
        {
            in = new StreamTokenizer(new BufferedReader(inputStream));
        }

        Double nextDouble() throws IOException
        {
            try
            {
                nextToken();
                return in.nval;
            }
            catch (EOFException e)
            {
                return null;
            }
        }

        Integer nextInt() throws IOException
        {
            try
            {
                nextToken();
                return (int) in.nval;
            }
            catch (EOFException e)
            {
                return null;
            }
        }

        Long nextLong() throws IOException
        {
            try
            {
                nextToken();
                return (long) in.nval;
            }
            catch (EOFException e)
            {
                return null;
            }
        }

        String nextString() throws IOException
        {
            try
            {
                nextToken();
                return in.sval;
            }
            catch (EOFException e)
            {
                return null;
            }
        }

        Character nextChar() throws IOException
        {
            try
            {
                nextToken();
                return in.sval.charAt(0);
            }
            catch (EOFException e)
            {
                return null;
            }
        }

        private void nextToken() throws IOException
        {
            if (in.nextToken() == StreamTokenizer.TT_EOF)
                throw new EOFException();
        }
    }
}