calancea

Calancea

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

Poveste şi cerinţă...

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.

h2. Date de intrare

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

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.
 

h2. Date de ieşire

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

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

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 |

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

| 3 6
10 5 1
| 5

|
h3. Explicaţie

...

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

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

9047