Calancea

calancea

== include(page="template/taskheader" task_id="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.

Poveste şi cerinţă...

h2. 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.
 

Fişierul de intrare $calancea.in$ ...

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

În fişierul de ieşire $calancea.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ B ≤ 10^15$
* Înălţimile iniţiale ale calăncilor vor fi din intervalul $[0, 10^9]$
 

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. calancea.in |_. calancea.out |

| 3 6
10 5 1
| 5

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

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

...

== include(page="template/taskfooter" task_id="calancea") ==

9047