calancea

Miruna a ajuns în fața unei noi provocări: în cetatea Devei a găsit $N$ calănci așezate în linie, fiecare calance având o anumită înălțime exprimată în centimetri. Înălțimea unei calănci poate fi crescută cu $1$ centimetru, însă această operație o costă exact $1$ leu. Operația de creștere poate fi aplicată aceleiași calănci de oricîte ori. Având un buget de $B$ lei la dispoziție, Miruna se întreabă câte subsecvențe ale șirului de calănci pot fi transformate astfel încât să devină monoton crescătoare.

Date de intrare

Pe prima line a fisierului calancea.in se vor afla numerele $N$ și $B$ , cu semnificaţia din enunț. Următoarele $N$ linii vor conţine câte un șir de lungime $N$ valori reprezentând înălțimile calăncilor.

Date de ieșire

În fișierul calancea.out se vor afișa un singur număr întreg reprezentând numărul de subsecvențe care pot fi transformate în șiruri monoton crescătoare având la dispoziție bugetul $B$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq B \leq 10^{15}$
• Înălțimile inițiale ale calăncilor vor fi din intervalul $[0, 10^{9}]$

Exemplu

calancea.in

3 6
10 5 1

calancea.out

5

Explicație

Cu excepția subsevenței $(1, 3)$, toate subsecvențele respectă proprietatea cerută.