Yazid 的新生舞会
题号：NC14502
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

这道题是没有舞伴的Yazid用新生舞会的时间出的。


Yazid有一个长度为n的序列A，下标从1至n。显然地，这个序列共有个子区间。
对于任意一个子区间[l,r]，如果该子区间内的众数在该子区间的出现次数严格大于（即该子区间长度的一半），那么Yazid就说这个子区间是“新生舞会的”。

所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。

现在，Yazid想知道，共有多少个子区间是“新生舞会的”。

输入描述:

第一行2个用空格隔开的非负整数n,type，表示序列的长度和数据类型。数据类型的作用将在备注中说明。
第二行n个用空格隔开的非负整数，依次为A1,A2,... ,An，描述这个序列。

输出描述:

输出一行一个整数，表示答案。
示例1

输入

复制 
5 0
1 1 2 2 3

输出

复制 
10

说明

“新生舞会的”子区间有[1,1],[1,2],[1,3],[2,2],[2,4],[3,3],[3,4],[3,5],[4,4],[5,5]共10个。

备注:

对于所有数据，保证 1≤n≤500000，0≤Ai≤n−1。
对于type=0的数据，没有任何特殊约定。
对于type=1的数据，保证Ai∈{0,1}。
对于type=2的数据，保证序列A的众数在整个序列中的出现次数不超过15。
对于type=3的数据，保证Ai≤7。