CF255C Almost Arithmetical Progression

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: - $ a_{1}=p $ , where $ p $ is some integer; - $ a_{i}=a_{i-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 $ s_{1},s_{2},...,s_{k} $ is a subsequence of sequence $ b_{1},b_{2},...,b_{n} $ , if there is such increasing sequence of indexes $ i_{1},i_{2},...,i_{k} $ $ (1

The first line contains integer $ n $ $ (1

Print a single integer — the length of the required longest subsequence.

In the first test the sequence actually is the suitable subsequence. In the second test the following subsequence fits: $ 10,20,10 $ .