Problem Description

Given a sequence $\{a_n\}$ and $k$, find how many subarrays $[l,r]$ satisfy $\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}$ is defined as the smallest non-negative integer that does not appear in the set.

Input Format

The first line contains two integers $n,k$ ($1\leq n\leq 5\times 10^5,0\leq k\leq n$).

The second line contains $n$ non-negative integers, where the $i$-th one is $a_i$ ($0\leq a_i\leq n$).

Output Format

One line with one number, representing the number of subarrays that satisfy the condition.

3 0
1 0 2

5

Hint

Translated by ChatGPT 5