Migrated from Lutece 2818 Niuma的rating

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$\texttt{Niuma}$闲来无事，于是打开了 $cf$，查看自己的 $rating$ 曲线，突然他发现自己的 $rating$ 曲线呈现出某种重复的特征，如图中所示，在 $A,B,C$ 连续的三段时间里，$A$ 段和 $C$ 段自己的$rating$曲线的趋势完全相同（即平移后可以重合）。现在$\texttt{Niuma}$有了一个奇怪的想法，他想固定 $B$ 段时间的长度，同时询问你 $rating$ 曲线中有多少个连续的子段，满足将其分解为 $A,B,C$ 三段后，$B$ 段的长度为给定的 $m$，且 $A,C$ 两段的变化趋势相同。

Input

第一行两个整数 $n,m$ ，表示$\texttt{Niuma}$总共打了 $n$ 次 $cf$ ，他希望固定的B段的时间长度为 $m$，你可以认为两次相邻的 $cf$ 之间的时间长度总是为 $1$ 第二行 $n$ 个正整数 $c_i$ 表示每次$rating$

Output

一行一个整数，表示满足条件的子段数量

Samples

15 2
1 1 3 2 8 8 8 4 6 5 5 5 1 3 2

3

Constraints

$1\le m \le n\le 3 \times 10^5$, $1\le c_i\le 10^9$

Note

对于样例，和题干中图例一样，满足条件的子段为$[5,13] , [6,14] , [7,15]$ 以 $[7,15]$ 这一段为例，可以发现以 $[10,12]$ 作为 $B$ 段（时间长度为 $2$ )，前后的趋势恰好相同，所以满足条件

Resources

2022 UESTC ICPC Training for String and Search Algorithm