描述

大家知道，黄药师不仅武功高超，而且酷爱音乐和诗歌。看到桃花岛来了个新客人，而且不是靠真武功进来的(见黄药师系列第 \(1\) 题进入桃花岛)，就准备为难为难你。

他写了一首\(N\)行诗句的诗歌，美中不足的是这些诗句并不押韵，黄药师非常想遵循古诗的押韵。诗歌被分为若干段，每段都是四行诗。每一句诗都有一个韵脚，假如\(A\)和\(B\)表示两种不同的韵脚，每段四行诗的韵脚只可能是 \(“AABB”, “ABAB”, “ABBA” \)和\(“AAAA”\)中的一种。

黄药师将诗句的韵脚都编了号，具有相同编号的句子代表有相同的韵脚。现在，黄药师想删掉一些句子，使得剩下的都是遵循押韵规则的四行诗，而且不允许改变诗句的顺序。

现在就问你：如何找出满足条件最长的诗歌？

格式

输入格式

第\(1\)行为一个整数\(N(1<=N<=4000)\)，代表黄药师写的诗歌的句子数。

第\(2\)行为\(N\)个整数，分别表示每一行诗的韵脚，这些数字都是不超过\(10^9\)的正数，每个数之间用\(1\)个空格隔开。

输出格式

一行一个整数\(k\)，为黄药师最多能够得到的四行诗个数。

样例1

样例输入1

15
1 2 3 1 2 1 2 3 3 2 1 1 3 2 2

样例输出

3

样例解释

删除第\(3、6、13\)句诗，就可以分成\(3\)个四行诗，分别为：

1 2 4 5

7 8 9 10

11 12 14 15