Yánshí

Bun $\dots$ - Sun Tzu

Task

On his daily walking trip to $\text{7-eleven}$, Ion Mergătorul got bored of tripping over rocks so he tripped over an array $A$ with $N$ integers and positive integer $K$. A subarray $A[i \dots j]$ is called suntzu if every element in the subarray appears at least $K$ times in the subarray. Ion wants to know how many suntzu subarrays are there in the array.

Input data

The first line of the input containts two integers $N$ and $K$ --- the size of the array and the positive integer $K$.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ --- the elements of the array.

Output data

The output should contain a single integer --- the number of suntzu subarrays in the array.

Constraints and clarifications

• $1 \leq N \leq 250 \ 000$
• $2 \leq K \leq N$
• $1 \leq A_i \leq N$ for all $1 \leq i \leq N$
• At Prosoft @ NT competition, the subtasks were worth $17, 22, 19, 16, 26$ points. The problem was configured using the IIOT score distribution for extra challenge.

Example

stdin

6 2
1 2 2 1 2 1

stdout

6

Explanation

The suntzu arrays are as follows: $A[1 \dots 4]$, $A[1 \dots 5]$, $A[1 \dots 6]$, $A[2 \dots 3]$, $A[2 \dots 6]$, $A[3 \dots 6]$