Description

Yazid has a sequence $A$ of length $n$, indexed from $1$ to $n$. Obviously, this sequence has $\frac{n\left( n+1\right)}{2}$ subarrays.

For any subarray $[l,r]$, if the mode in this subarray has a frequency strictly greater than $\frac{r-l+1}{2}$ (that is, more than half of the subarray's length), then Yazid calls this subarray "Freshman Ball".

The mode is the value that appears most frequently in the subarray. In particular, if multiple values tie for the highest frequency, we define the smallest value as the mode.

Now Yazid wants to know how many subarrays are "Freshman Ball".

Input Format

The first line contains two space-separated nonnegative integers $n, type$, representing the length of the sequence and the data type. The role of the data type will be explained in the Hint.

The second line contains $n$ space-separated nonnegative integers, namely $A_1, A_2, ..., A_n$, describing the sequence.

Output Format

Output a single integer on one line, representing the answer.

5 0
1 1 2 2 3

10

Hint

【Sample Explanation #1】

The "Freshman Ball" subarrays are $[1,1],[1,2],[1,3],[2,2],[2,4],[3,3],[3,4],[3,5],[4,4],[5,5]$, for a total of $10$.

Constraints:

For all testdata, it is guaranteed that $0\leq A_i\leq n-1$.

For $type=0$ testdata, there is no special stipulation.

For $type=1$ testdata, it is guaranteed that $A_i\in \{ 0, 1 \}$.

For $type=2$ testdata, it is guaranteed that the mode of sequence $A$ appears at most $15$ times in the entire sequence.

For $type=3$ testdata, it is guaranteed that $A_i\leq 7$.

From CodePlus 2017 November Contest, produced by the Student Algorithms and Competitions Association, Department of Computer Science and Technology, Tsinghua University.

Credit: idea/Zheng Linkai, problem setting/Wang Yuzhong, problem checking/Zheng Linkai.

Git Repo: https://git.thusaac.org/publish/CodePlus201711

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5