P10169 [DTCPC 2024] mex,min,max

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.

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$).

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

Translated by ChatGPT 5