题目描述

给定一个长度为 N 的数组。请计算有多少个连续子数组存在多数元素。

对于一个长度为 K 的数组，若某个值出现次数至少为 floor(K/2)+1，则称该值为多数元素。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示数组元素。

输出格式

输出一个整数，表示存在多数元素的连续子数组数量。

数据范围与约定

• 1 <= N <= 250000；
• 所有数组元素都在 1..N 之间；
• 连续子数组由原数组中连续的一段位置唯一确定。

样例

6
1 2 1 2 3 2

10

样例解释

所有长度为 1 的子数组都有多数元素；除此之外还有 4 个连续子数组有多数元素。