3. Liečivá alpa

V Anurovej lekárničke pribudla mocná zbraň – všeliek všetkých otvorených zranení, všemocná alpa¹. Tak sa mu osvedčila a zapáčila, že ampuliek alpy nosí so sebou vždy nekonečne veľa.

V sobotu sa, tak ako asi všetci, zabával na gladiátorských hrách. Tak veľmi sa mu tam páčilo, až sa rozhodol, že ani porazení gladiátori si nezaslúžia zomrieť. Preto hneď, ako dotlieskal, zoskočil z tribúny a vytiahol alpu, odhodlaný vyliečiť čo najviac bojovníkov.

Každý bojovník má niekoľko zranení, ktoré treba vyliečiť. Ak ostane bojovníkovi čo i len jedno zranenie nevyliečené, dostane infekciu a zomrie tak či tak. Na vyliečenie hocijakého zranenia stačí jedna kvapka alpy. Keďže alpa je balená v znovu neuzatvárateľných obaloch, Anura má teraz veľkú dilemu:

Chce vyliečiť čo najviac bojovníkov. Zároveň si však alpu veľmi váži² a teda ak nejakú jej ampulku otvorí, chce ju celú do poslednej kvapky minúť (zužitkovať, nie premrhať vyhodením, alebo kvapnutím na už zahojenú ranu). Anura nemá to srdce prejsť počas liečenia okolo bojovníka a nevyliečiť ho. Teda ak niekde začne liečiť, bude postupne za radom liečiť všetkých bojovníkov, až k nejakému, od ktorého potom nenápadne odíde, snažiac sa nemyslieť na ostatných nevyliečených.

Úloha

V rade vedľa seba stojí \(n\) bojovníkov čakajúcich na vyliečenie. O každom bojovníkovi vieme jeho počet zranení \(z_i\), a teda aj počet kvapiek alpy potrebných na jeho zachránenie.

V každej ampulke je \(a\) kvapiek alpy. Zistite, aký najdlhší súvislý úsek bojovníkov môže Anura vyliečiť bez toho, aby čo i len kvapka alpy vyšla nazmar. Počet použitých ampuliek nás nezaujíma.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú medzerou oddelené prirodzené čísla \(n\) a \(a\) (\(1 \leq n, a \leq 100\,000\)) – počet zranených bojovníkov a počet kvapiek v jednej ampulke alpy. Nasleduje \(n\) riadkov, v \(i\)-tom z nich sa nachádza prirodzené číslo \(z_i\) (\(1 \leq z_i \leq 10^9\)) – počet zranení \(i\)-teho bojovníka zľava.

Formát výstupu

Na jediný riadok výstupu vypíšte maximálny počet bojovníkov, ktorých sa dá za daných podmienok vyliečiť.

Príklady

Input:

5 9
1
2
3
4
5

Output:

3

Troch vyliečime, ak začneme liečiť druhého bojovníka a skončíme predposledným.

Input:

6 2
3
4
1
2
4
3

Output:

5

Napríklad vyliečime prvých piatich.

Input:

5 22
9
1
6
2
3

Output:

0

Je nám to ľúto, ale nie sme ochotní premrhať čo i len kvapku.