E. 十六行诗
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

无趣的书呆子、讨人厌的优等生，好的坏的都来自于她。十六行诗从未写出任何一句真正的诗，她也从未见过真正的世界。

十六行诗不会写诗，她让 LLM 帮忙生成了 $$$n$$$ 句诗，每句诗有一个特定的韵脚 $$$a_i$$$。

十六行诗认为，只有满足 AABB, ABAB, ABBA 这三种形式韵脚的诗才是真正的诗（A，B 可以相同）。

十六行诗可以从生成的 $$$n$$$ 句诗中删去一些句子，使得剩下的句子，连续的按照每四句一组划分为一首诗，每首诗都能满足上述三种形式之一。

十六行诗想知道，她尽可能少的删去句子后，剩下的句子，能构成多少首诗。

Input

第一行一个整数 $$$n(1\le n \le 500)$$$，表示生成的诗一共有 $$$n$$$ 句。

第二行 $$$n$$$ 个整数，第 $$$i$$$ 个整数表示第 $$$i$$$ 句诗的韵脚 $$$a_i(1\le a_i\le 10^9)$$$。

Output

输出一个整数，表示十六行诗最多能构成多少首诗。

Examples
Input
14
1 1 1 1 2 1 1 3 2 4 5 4 5 5
Output
3
Input
15
2 3 1 2 3 2 3 1 1 3 2 2 1 3 3
Output
3
Input
8
1 1 1 2 2 1 3 3
Output
1