K-mins

A sequence $A=[A_1, A_2, \dots, A_N]$ of length $N$ is given. For any two integers $i$ and $j$ with $1 \leq i < j \leq N$, $A_i \neq A_j$ holds.

For two integers $l$ and $r$ with $1 \leq l \leq r \leq N$, define $f(l,r)$ as follows.

$f(l,r)$ is the $K$-th smallest value among $A_l, A_{l+1}, \dots, A_r$.

If the length of the interval, $r-l+1$, is less than $K$, then $f(l,r)=0$.

Compute $\sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r)$.

The first line contains the number of elements $N$ and the integer $K$, separated by a space. ($1 \leq N \leq 100\,000$; $1 \leq K \leq 10$)

The second line contains the $N$ integers $A_1, A_2, \dots, A_N$, separated by spaces. ($-10^9 \leq A_i \leq 10^9$)

Print the value of $\sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r)$.