Vynálezca Denis vymyslel novú techniku lovu - vyhliadne si vhodnú vodnú priehradu, priplaví sa k nej na člne, a pripevní na ňu svoju špeciálnu sieť na úrovni vodnej hladiny. Potom odpláva, niekoľko hodín počká, priplaví sa naspäť k sieti a zoberie si ju aj s úlovkom.
Hladina vody pri priehrade sa však neustále mení, a keď je sieť pod alebo nad vodnou hladinou, nedá sa odpojiť. Denis preto potrebuje svet presvedčiť že jeho technika lovu je nielen cool, ale aj praktická - teda že napriek meniacej sa výšky hladiny vody pri priehrade existuje veľa príležitostí kedy sa dá sieť pripveniť tak, aby sa do rozumného času dala aj odpojiť.
Na začiatku je výška hladiny vody pri priehrade veľa metrov nad morom, kde veľa je veľa. Každú hodinu sa výška hladiny zmení o nejaký celočíselný počet metrov (možno aj 0). Spočítajte koľko existuje takých rôznych hodín $x<y$ že výška hladiny počas nich bola rovnaká, a $y-x\, \leq \,k$, teda že od pripevnenia siete netreba čakať viac ako $k$ hodín do jej odpojenia.
V prvom riadku sú dve celé čísla $n$ a $k$, $1 \leq k \leq n \leq 10^6$ - najväčšia tolerovaná doba čakania od pripevnenia siete do jej odpojenia a počet hodín, o ktorých máme záznamy zmien výšky hladiny.
V druhom riadku je $n$ celých čísel $-10^9 \leq h_i \leq 10^9$ - zmena výšky vodnej hladiny po $i$-tej hodine. Pripomíname, že vodná hladina začína v hodine 0 vo výške veľa.
Jedno celé číslo - počet dvojíc čísel $x<y$, kde $y-x \leq k$ a výška hladiny bola počas hodiny $x$ a $y$ rovnaká.
5 3
10 -5 -5 5 5
2
Hladina je v rovnakej výške v hodinách $(0,3)$, $(2,4)$ a $(1,5)$. Keďže $5-1>3$, odpoveď je $2$.
8 4
-3 4 2 -2 0 1 1 -2
6
9 4
0 0 0 0 0 0 0 0 0
30