kami

Kami

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

Poveste şi cerinţă...

Pe muntele din Athos se afla $N$ nivele. Pentru fiecare nivel se cunoaste cantitatea de zapada $z{~i~}$ aflata acolo. Zeus poate sa dea cu fulgerul pe un nivel si sa provoace o avalansa care porneste de acolo. Fenomenul de avalansa dintr-un nivel $i$ se desfasoara in felul urmator: zapada de pe nivelul $i$ coboara pe nivelul $i - 1$. Daca cantitatea de zapada de pe nivelul $i - 1$ este mai mare sau egala decat cantitatea de zapada de pe nivelul $i$, atunci avalansa se opreste. Daca nu, cantitatile de zapada se aduna si avalansa continua mai departe cu un nivel mai jos. Se dau $M$ operatii de $2$ tipuri:
 
$0 x val$ - Poseidon schimba valoarea de pe nivelul $x$ cu $val$
$1 b$ - Athena vrea sa stie daca Zeus ar da cu fulgerul in nivelul $b$ si ar provoca o avalansa de acolo, care ar fi nivelul $a$ in care s-ar opri avalansa?

h2. Date de intrare

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

Fişierul de intrare $kami.in$ va contine pe prima linie $N$. Pe linia $2$ vor fi $N$ numere naturale reprezentand $z{~i~}$. Pe linia $3$ va fi $M$ iar pe urmatoarele $M$ linii cele $M$ operatii.

h2. Date de ieşire

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

Fişierul de ieşire $kami.out$ va contine cate un raspuns pentru fiecare intrebare data de Athena reprezentand pozitia unde se opreste avalansa. Daca avalansa nu se opreste nici macar in pozitia $1$, consideram ca se opreste in $0$.

h2. Restricţii

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

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* $1 ≤ z{~i~} ≤ 1.000.000.000$

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

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

|5
10 4 1 2 3
4
1 4
1 5
0 1 9
1 5
|2
1
0

|

h3. Explicaţie
 
...
 

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

1460