pinball

Por Costel si Pinball

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

Poveste şi cerinţă...

Por Costel se joaca pinball. Dupa multe ore de studiat jocul prin lovituri repetate ale mesei de pinball cu ratul, Por Costel crede ca s-a prins cum functioneaza.
 
Exista N spring-uri pe masa de pinball, care au rolul de a lansa bila mai departe. Imaginandu-ne o vedere “de sus” a mesei, springul i este al i-lea spring de la stanga la dreapta, adica pe orizontala. Acum, spring-urile sunt caracterizate si de pozitia lor pe verticala. Anume, al <tex>i</tex>-lea spring are o coordonata verticala <tex>v_i</tex>.
 
Daca bila se loveste de un spring <tex>i</tex>, acesta o lanseaza catre un alt spring <tex>j</tex>, <tex>j</tex> > <tex>i</tex>. Spunem, in acest caz, ca bila ricoseaza din spring-ul <tex>i</tex> in spring-ul <tex>j</tex>. Exista doua posibilitati:
 
* ricosare in sus: <tex>v_j</tex> > <tex>v_i</tex>, numai daca ultima ricosare a fost in jos.
* ricosare in jos: <tex>v_j</tex> < <tex>v_i</tex>, numai daca ultima ricosare a fost in sus.
 
Prima ricosare nu are nicio restrictie: Por Costel lanseaza bila catre primul spring, iar din acesta ea ricoseaza fie in sus fie in jos. Punctajul pe care il obtine Por Costel la o lansare este numarul de spring-uri din care ricoseaza bila. O data ce ea a trecut de ultimul spring, tura s-a terminat.
 
Por Costel a petrecut foarte mult timp calculand punctajul maxim pe care il poate obtine lansand bila corect. Insa, ce nu stie el e ca faptul ca loveste masa din cand in cand face ca unele spring-uri sa-si modifice coordonata verticala <tex>v_i</tex>. Ajutati-l pe Por Costel sa calculeze in fiecare moment punctajul maxim pe care il poate obtine.

h2. Date de intrare

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

Fişierul de intrare $pinball.in$ va contine pe prima linie numarul <tex>N</tex>. A doua linie va contine un sir de <tex>N</tex> numere intregi <tex>v</tex>. A treia linie va contine numarul <tex>M</tex> iar urmatoarele <tex>M</tex> linii vor contine cate doua numere <tex>x</tex> si <tex>y</tex> reprezentand o modificare astfel: spring-ul <tex>x</tex> capata coordonata verticala <tex>y</tex> (<tex>v_x = y</tex>)

h2. Date de ieşire

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

În fişierul de ieşire $pinball.out$ se vor afla <tex>M+1</tex> linii. Prima linie contine raspunsul pentru starea initiala a vectorului. Apoi, avem <tex>M</tex> linii cu raspunsul dupa fiecare din cele <tex>M</tex> modificari.

h2. Restricţii

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

* <tex>1</tex> &le; <tex>N</tex>, <tex>M</tex> &le; <tex>10^6</tex>
* <tex>1</tex> &le; <tex>v_i</tex>, <tex>y</tex> &le; <tex>10^9</tex>
* <tex>1</tex> &le; <tex>x</tex> &le; <tex>N</tex>
* Se garanteaza ca nu vor exista <tex>i</tex> si <tex>j</tex> astfel incat <tex>v_i = v_j</tex> atat in sirul initial cat si pe parcursul celor <tex>M</tex> operatii

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

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

| 10
1 10 2 5 6 3 4 8 9 7
3
1 11
7 17
8 12
| 7
6
8
6

|

h3. Explicaţie
 
...
 

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

10331