!>problema/cumainilecurate?miclovan_roman.jpg!

bq. - Gangsterii noştrii nu sunt ca cei americani - ai noştrii nu au tradiţie!
- Sper că n-o să-i lasaaƒm să şi-o formeze!
- Fără îndoială, şi totuşi în ultima vreme au apărut bande care folosesc arme, cele care vi le-am spus şi încă câteva care am reuşit să le lichidez, împotrivaƒ lor nu găseşti nici martori, nici dovezi. Eu am o metodă simplム- mムbazez cムmajoritatea dintre ei sunt nervoşi şi isterici, fac de aşa manieră să pună mâna pe arme, şi apoi cine trage primul ... şi cum la treaba asta mă cam pricep ... îmi şi place, recunosc!

bq. - Gangsterii noştrii nu sunt ca cei americani - ai noştrii nu au tradiţie!
- Sper că n-o să-i lasaăƒm să şi-o formeze!
- Fără îndoială, şi totuşi în ultima vreme au apărut bande care folosesc arme, cele care vi le-am spus şi incă câteva care am reuşit să le lichidez, impotrivaƒ lor nu găseşti nici martori, nici dovezi. Eu am o metodă simplム- mムbazez cムmajoritatea dintre ei sunt nervoşi şi isterici, fac de aşa manieră să pună mână pe arme, şi apoi cine trage primul ... şi cum la treabă asta mă cam pricep ... îmi şi place, recunosc!

bq. - Deci să repetăm: Ajungem la Semaca ... prin Buciurligă.
- Ăla cu jaful furgonetei?

- Rivalul lui Semaca, iar la Buciurliga ajungem prin Pascu, mâna lui dreapta. Aprobi schema?

- Rivalul lui Semaca, iar la Buciurligă ajungem prin Pascu, mână lui dreaptă. Aprobi schema?

- S-o aprobăm!

Doar că lucrurile nu aveau cum să fie atât de simple - legătură dintre Buciurligaƒ şi Semaca avea să se facă prin Laƒscaƒricăƒ. Iar înainte de a-l lichidă pe Semaca, comisarii Roman şi Miclovan au trebuit mai întâi să se ocupe de monstruoasa să coaliţie de gangsteri: Pleoarcaƒ, Şchiopu şi Burdujel.

Doar că lucrurile nu aveau cum să fie atât de simple - legătura dintre Buciurligムşi Semaca avea să se facă prin Lăƒscăƒricăƒ. Iar înainte de a-l lichida pe Semaca, comisarii Roman şi Miclovan au trebuit mai întâi să se ocupe de monstruoasa sa coaliţie de gangsteri: Pleoarcăƒ, Şchiopu şi Burdujel.

Pentru a simplifica lucrurile pe viitor, activistul de partid a întocmit o lista cu priorităţile din sectorul lor - mai exact, cele mai relevante minţi criminale ordonate după importantă lor în ochii conducerii. După cum se întâmplă des în practică, idealurile conducerii şi cele ale subalternilor diferă, aşa că, folosindu-şi flerul, Miclovan a scris în dreptul fiecărui gangster "adevărată" să importanţă, sub forma unui număr întreg pozitiv.
 
Comisarii au decis **de comun acord** să elimine mafioţi în ordine crescătoare a importanţei lor reale pentru uşurinţă în exerciţiul funcţiei şi pentru a semăna panică printre gangsteri. Totuşi, ei nu ar dori să şi-l pună în cap pe secretarul de partid - ei vor suprima figuri numai în ordine crescătoare a priorităţilor oficiale. De asemenea, pentru a elimina o parte cât mai mare a activităţii infracţionale, ei vor parcurge lista primită în ordine crescătoare a indicilor, alegând să elimine un mafiot de fiecare dată când el are o importantă strict mai mare decât a ultimului eliminat (voi, fiind informaticieni premiaţi, ştiţi că acesta nu este neapărat cel mai bun algoritm posibil pentru a efectua alegerile).
 
A fost război, valorile s-au răsturnat, atacurile cu mâna armată au devnit o normalitate, aşa că gestiunea situaţiei Bucureştiului a devenit o problema fundamentală consumatoare de timp - Comisarii vă cer ajutorul în scrierea unui program care să automatizeze următoarele operaţii:
 
* În urma unor evenimente importante (precum jefuirea Bijuteriei Lembert) importanţă unei figuri se modifică - $1 pos val$ - importantă celui de-al $pos$-ulea criminal de pe lista devine $val$.
* $2 val$ - Comisarii vor să ştie **dacă** ar fi să elimine începând cu gangsterul de pe poziţia $pos$, folosind metoda menţionată, câţi mafioţi ar fi suprimaţi?
 
 
h2. Date de intrare
 
Pe prima linie a fişierului de intrare $cumainilecurate.in$ se află două numere întregi $N$ şi $M$, separate printr-un spaţiu, semnificând numărul de gangsteri de pe lista primită şi respectiv numărul de interogări.
Pe a doua linie se află $N$ numere întregi pozitive separate prin câte un spaţiu, reprezentând importanţa fiecărui mafiot de pe lista, în ordine.
Următoarele $M$ linii au fiecare una din structurile $1 pos val$ sau $2 pos$, cu semnificaţiile din enunţ.
 
 
h2. Date de ieşire
 
Fişierul $cumainilecurate.out$ trebuie să conţină atâtea linii câte operaţii de tipul $2$ sunt în fişierul de intrare, fiecare linie reprezentând răspunsul pentru operaţia de tipul $2$ corespunzătoare din input.
 
 
h2. Restricţii si precizări
 
* $1 ≤ N ≤ 10^5^$
* $1 ≤ M ≤ 6 * 10^4^$
* $1 ≤ importanţa unui mafiot ≤ 10^9^$
* **Full feedback!**
* **Atenţie!** Volum mare de date de intrare, va recomandăm să optimizaţi citirea folosindu-va de "acest cod":http://pastebin.com/kSM2CRBq.
* **Subtask 1 (20 puncte)**: $1 ≤ N ≤ 3000$ şi $1 ≤ M ≤ 2000$
* **Subtask 2 (20 puncte)**: Se garantează că în input vor fi cel mult $10$ operaţii de tipul $1$.
* **Subtask 3 (60 puncte)**: Restricţii iniţiale
 
h2. Exemplu
 
table(example). |_. cumainilecurate.în |_. cumainilecurate.out |
| 5 11
1 5 3 4 2
2 1
2 2
2 3
2 4
2 5
1 2 2
2 1
2 2
2 3
2 4
2 5
|2
1
2
1
1
4
3
2
1

Pentru a simplifica lucrurile pe viitor, activistul de partid a întocmit o listă cu priorităţile din sectorul lor - mai exact, cele mai relevante minţi criminale ordonate după importanţa lor în ochii conducerii. După cum se întâmplă des în practică, idealurile conducerii şi cele ale subalternilor diferă, aşa că, folosindu-şi flerul, Miclovan a scris în dreptul fiecărui gangster "adevărata" sa importanţă, sub formă unui număr întreg pozitiv.
 
Comisarii au decis **de comun acord** să elimine mafioţi în ordine crescătoare a importanţei lor reale pentru uşurinţă în exerciţiul funcţiei şi pentru a semăna panică printre gangsteri. Totuşi, ei nu ar dori să şi-l pună în cap pe secretarul de partid - ei vor suprima figuri numai în ordine crescătoare a priorităţilor oficiale. De asemenea, pentru a elimina o parte cât mai mare a activităţii infracţionale, ei vor parcurge lista primită în ordine crescătoare a indicilor, alegând să elimine un mafiot de fiecare data când el are o importanţă strict mai mare decât a ultimului eliminat (voi, fiind informaticieni premiaţi, ştiţi că acesta nu este neapărat cel mai bun algoritm posibil pentru a efectua alegerile).
 
A fost război, valorile s-au răsturnat, atacurile cu mâna armată au devnit o normalitate, aşa că gestiunea situaţiei Bucureştiului a devenit o problemă fundamentală consumatoare de timp - Comisarii vă cer ajutorul în scrierea unui program care să automatizeze următoarele operaţii:
 
* În urma unor evenimente importante (precum jefuirea Bijuteriei Lembert) importanţa unei figuri se modifică - $1 pos val$ - importanţa celui de-al $pos$-ulea criminal de pe listă devine $val$.
* $2 val$ - Comisarii vor să ştie **dacă** ar fi să elimine începând cu gangsterul de pe poziţia $pos$, folosind metoda menţionată, câţi mafioţi ar fi suprimaţi?
 
 
h2. Date de intrare
 
Pe prima linie a fisierului de intrare $cumainilecurate.in$ se afla doua numere intregi $N$ si $M$, separate printr-un spatiu, semnificand numarul de gangsteri de pe lista primita si respectiv numarul de interogari.
Pe a doua linie se afla $N$ numere intregi pozitive separate prin cate un spatiu, reprezentand importanta fiecarui mafiot de pe lista, in ordine.
Urmatoarele $M$ linii au fiecare una din structurile $1 pos val$ sau $2 pos$, cu semnificatiile din enunt.
 
 
h2. Date de ieşire
 
Fisierul $cumainilecurate.out$ trebuie sa contina atatea linii cate operatii de tipul $2$ sunt in fisierul de intrare, fiecare linie reprezentand raspunsul pentru operatia de tipul $2$ corespunzatoare din input.
 
 
h2. Restricţii
 
* $1 ≤ N ≤ 10^5^$
* $1 ≤ M ≤ 6 * 10^4^$
* $1 ≤ importanta unui mafiot ≤ 10^9^$
* **Atentie!** Volum mare de date de intrare, vă recomandăm să optimizaţi citirea folosindu-va de "acest cod":http://pastebin.com/kSM2CRBq.
* **Subtask 1 (20 puncte)**: $1 ≤ N ≤ 3000$ si $1 ≤ M ≤ 2000$
* **Subtask 2 (20 puncte)**: Se garanteaza ca in input vor fi cel mult $10$ operatii de tipul $1$.
* **Subtask 3 (60 puncte)**: Restrictii initiale
 
h2. Exemplu
 
table(example). |_. cumainilecurate.in |_. cumainilecurate.out |
| 5 11
1 5 3 4 2
2 1
2 2
2 3
2 4
2 5
1 2 2
2 1
2 2
2 3
2 4
2 5
|2
1
2
1
1
4
3
2
1

1
|

h3. Explicaţie

h3. Explicaţie
 
Pentru primele $5$ interogari acestia sunt gangsterii alesi:
$**1** **5** 3 4 2$ _(aici se vede clar ca strategia calculata a comisarilor nu este chiar cea mai buna, varianta optima fiind, de fapt, $**1** 5 **3** **4** 2$)_
$1 **5** 3 4 2$
$1 5 **3** **4** 2$
$1 5 3 **4** 2$
$1 5 3 4 **2**$
 
Dupa modificarea importantei mafiotului cu numarul de ordine $2$, lista arata in felul urmator:
$1 2 3 4 2$
 
Pentru urmatoarele $5$ interogari acestia sunt gangsterii alesi:
$**1** **2** **3** **4** 2$ _(se observa ca de aceasta data strategia comisarilor este cea corecta)_
$1 **2** **3** **4** 2$
$1 2 **3** **4** 2$
$1 2 3 **4** 2$
$1 2 3 4 **2**$

Pentru primele $5$ interogări aceştia sunt gangsterii aleşi:
$**1** **5** 3 4 2$ _(aici se vede clar că strategia calculată a comisarilor nu este chiar cea mai bună, varianta optimă fiind, de fapt, $**1** 5 **3** **4** 2$)_
$1 **5** 3 4 2$
$1 5 **3** **4** 2$
$1 5 3 **4** 2$
$1 5 3 4 **2**$
 
După modificarea importanţei mafiotului cu numărul de ordine $2$, lista arată în felul următor:
$1 2 3 4 2$
 
Pentru următoarele $5$ interogări aceştia sunt gangsterii aleşi:
$**1** **2** **3** **4** 2$ _(se observă că, de această dată, strategia comisarilor este cea corectă)_
$1 **2** **3** **4** 2$
$1 2 **3** **4** 2$
$1 2 3 **4** 2$
$1 2 3 4 **2**$

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