题目描述

给定序列 $\{a_n\}$ 和 $k$，求有多少子区间 $[l,r]$ 满足 $\operatorname{mex}\{a_l,a_{l+1},\dots,a_{r-1},a_r\}+\min\{a_l,a_{l+1},\dots,a_{r-1},a_r\}+k\geq \max\{a_l,a_{l+1},\dots,a_{r-1},a_r\}$。

$\operatorname{mex}$ 定义为集合内没有出现过的最小的非负整数。

输入格式

第一行两个整数 $n,k$（$1\leq n\leq 5\times 10^5,0\leq k\leq n$）。

第二行 $n$ 个非负整数，第 $i$ 个表示 $a_i$（$0\leq a_i\leq n$）。

输出格式

一行一个数，表示满足条件的子区间个数。

3 0
1 0 2

5