在遥远的杜洛克（Duloc）大陆，史莱克（Shrek）在古老的沼泽之歌中发现了一段神奇的旋律。然而，这段旋律是由一串代表青蛙叫声和树叶沙沙声的数字序列组成的。为了解开其中的秘密，史莱克需要根据一套特定的规则，解码出这段神秘序列中最长的重复模式。

史莱克的旋律序列 $s$ 由各种声音组成，每种声音用一个整数表示。这首歌总共包含 $n$ 个声音。

史莱克需要找到满足“严格杜洛克和声”的最长子序列。为了符合杜洛克和声，必须满足以下条件：所选子序列中的每一个声音，都必须在子序列中拥有一个与自身相同的邻居。

更准确地说，史莱克必须确定 $s$ 的最长子序列（不一定是连续位置）$x_1x_2 \dots x_k$，使得对于所有 $1 \le i \le k$，满足 $x_i = x_{i-1}$ 或 $x_i = x_{i+1}$，或者两者同时满足。

例如，史莱克可以选择子序列 $[1, 1, 1, 2, 2]$ 或 $[4, 4, 4, 4, 4]$，但不能选择 $[1, 2, 2, 1, 1]$，因为第一个声音没有相同的相邻声音。

请帮助史莱克解开这段迷人的旋律！

输入格式

第一行包含一个整数 $n$ —— 史莱克歌曲中声音的数量。 第二行包含整数值 $s_1, s_2, \dots, s_n$，代表史莱克歌曲中的声音。

数据范围

$1 \le n \le 10^6$ $-10^9 \le s_i \le 10^9$

输出格式

第一行输出一个整数 —— 满足题目所述性质的最长子序列的长度。如果没有这样的子序列，输出 0。

样例

样例输入 1

9
1 2 3 1 3 1 2 3 2

样例输出 1

5

样例输入 2

6
3 4 10 1 -3 5

样例输出 2

0

样例输入 3

4
1 2 1 1

样例输出 3

3

说明

在第一个样例中，满足题目所述性质的最长子序列是 $s_1s_4s_6s_7s_9 = [1, 1, 1, 2, 2]$。 在第二个样例中，不存在满足这些性质的子序列。