题目描述

译自 ROI 2013 Day2 T3. Массовый прогноз

在学校计算机俱乐部主席选举中，有 $K$ 位候选人和 $N$ 位选民。候选人编号为 $1$ 到 $K$，选民编号为 $1$ 到 $N$。

根据投票结果，生成一个列表，第 $i$ 个元素表示第 $i$ 位选民投票支持的候选人编号。对于列表的每个子区间，安排一名观察员统计该区间的投票结果。因此，选举中共有 $\frac{N(N + 1)}{2}$ 名观察员。

如果观察员发现某候选人在其负责的区间内获得的票数超过半数，他会在社交网络上发布预测，认为该候选人将赢得选举。

你需要编写一个程序，根据投票列表计算观察员发布的预测数量。

输入格式

输入文件的第一行包含两个整数 $N$ 和 $K$ ($1 \leq N \leq 500000$, $1 \leq K \leq 500000$)。

第二行包含 $N$ 个整数 $V_1, V_2, \ldots, V_N$ ($1 \leq V_i \leq K$)，表示选民的投票列表。

输出格式

输出文件应包含一个整数，表示预测的数量。

样例 1

输入

5 2
1 2 1 2 1

输出

9

样例 2

输入

3 7
5 2 6

输出

3

数据范围与提示

本题包含 $50$ 个独立测试点，每个测试点价值 $2$ 分，总分为 $100$ 分。测试点的评分是独立的，具体限制条件如下表所示：