长度为k的区间满足"顺子"的充要条件:

1.具有k个不同的数

2.该区间的最大值减最小值为:k-1

做法：

用ST表查询区间最大值和最小值

题目内容

小红最近喜欢研究顺子，顺子的定义为：排序后相邻两元素的差的绝对值恰好等于 1。

现在有人给小红一个长度为 $n$ 的数组，他问小红有多少长度为 $k$ 的子区间满足：子区间中元素恰好构成一个顺子？

但是小红最近没有时间帮他解决这个问题，你能帮帮他吗？

例如，对于数组 $[3, 7, 6, 4, 5]$， 子数组 $[4, 5]$ 是一个顺子。

备注：

子区间可以理解为从原数组中从头部或尾部选择一些元素删掉（或者不删）并保持剩余元素的相对位置不变。

输入描述

第一行两个整数 $n$ 和 $k$ ， $1\le k\le n\le 300000$

第二行 $n$ 个整数， $a_1,a_2,...a_n$ （ $1\le a_i \le10^6$ ）

输出描述

输出一个正整数代表答案。

样例

样例一

输入

4 2
1 2 3 4

输出

3

样例解释

满足条件的区间有 $[1,2]$ 和 $[2,3]$ 还有 $[3,4]$ 。

样例二

输入

6 3
1 3 5 4 6 2

输出

2