题目描述

在一片神秘的宝藏之地，有 $n$ 位探险家站成一排，每位探险家心中都有一个自己最想去的宝藏地点（用 $a_i$ 表示）。

现在，他们想要组成若干支寻宝小队，每支小队必须是连续的一段相邻的探险家，并且在这段队伍中，有超过一半的人想去同一个地点（即该地点是这段队伍的“绝对众数”），这样他们就可以一起去那个地点寻宝。

每支小队至少要有两个人（因为一个人没法组队），并且不同的小队之间不能有重叠的成员（即小队是互不相交的）。请问，最多可以组成多少支这样的寻宝小队？

注意，可能不存在满足条件的寻宝小队，此时答案为 $0$。

形式化地，设 $f(l,r)$ 为子区间 $[l,r]$ 中出现次数最多的数字出现的数量，你需要选出尽可能多的区间 $[l_1,r_1],[l_2,r_2],...,[l_k,r_k]$ 满足 $l_1<r_1<l_2<r_2<...<l_k<r_k$，且 $f(l_i,r_i) > \frac{r_i - l_i + 1}{2}$ $(i = 1,2,...,k)$。

输入格式

第一行一个正整数 $n$，表示探险家数量。

接下来一行 $n$ 个整数 $a_i$，表示每位探险家想去的宝藏地点。

输出格式

一个整数，表示答案。

6
1 1 4 5 1 4

1

7
1 2 1 2 3 2 3

2

样例解释

第一组样例，可以选择 $[1,2]$ 或者 $[1,5]$，答案为 $1$，容易证明，最多只能组成一个寻宝小队。

第二组样例，可以选择 $[1,3],[4,6]$，答案为 $2$，容易证明没有比 $2$ 更大方案。

数据规模与约定

下发文件

下发文件对应子任务 $1,2,3$。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^6,1 \leq a_i \leq 10^9$ 。