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 indexesi1,?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.

  Sample test(s) 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.

  
  

  题意：从给定的有序的序列中找最多的p，q，p，q.

  
  

  
  

  dp[i][j]:代表在第 i 个数前一个数是 j 的情况下的最多值，

  则：

  dp[i][j]=dp[j][pre] + 1,

  
  

  #include
      
       
  #include
       
         #include
        
          #include
         
           #include