8. O()kúzlení

Udalosti spomínané v tomto zadaní sú založené na pravdivých faktoch. Však si vyžiadaj vystúpenie, keď ho najbližšie stretneš.

Komu z nás sa nepáči mágia? Rýchle prsty, odvádzanie pozornosti a na prvý pohľad neuskutočniteľné veci? Niet divu, že aj Mišof sa v svojej mladosti naučil zopár trikov, ktoré teraz predvádza na skrátenie dlhej chvíle alebo na machrovanie v krčme.

Pozná pár kartových trikov, necháva miznúť zápalky a rôzne iné predmety, na povrazoch sa objavujú všelijaké uzly a dokonca dokáže opraviť roztrhnutú bankovku. Ako to robí? To ti, samozrejme, nemôžem povedať. Chápeš, tajomstvo kúzelníka.

Nedávno sa Mišof naučil nový trik a preto ti ho chcel predviesť. Do radu postavil \(n\) nepriehľadných pohárov otočených hore dnom. Pod niektoré z nich položil guličku. Spýtal sa ťa na súvislý interval pohárov a začal odkrývať, čo sa nachádza pod nimi. Na tvoje prekvapenie pod každým z vybraných pohárov bolo presne to, čo si neočakával. Ak tam na začiatku gulička bola, teraz tam nie je a naopak. Uau. Potom guličky opäť zakryl a postup opakoval s novým intervalom. Si okúzlený?¹

“A to nie je všetko!” chváli sa Mišof. “Tiež ti viem ukázať najdlhšiu, nie nutne súvislú podpostupnosť pohárov, v ktorej sa pod pohármi najskôr guličky nenachádzajú a potom sa tam už stále nachádzajú.”

“Ale však to nie je ťažké.” Povieš a po chvíli premýšľania ukážeš správnu podpostupnosť.

“Áno? A dokážeš to, aj keď ti zmením tento interval, aj tento a nakoniec aj tento?” nedá pokoj Mišof.

No čo, dokážeš?

Úloha

Na vstupe dostaneš popis postupnosti a zmeny, ktoré nastali. Každá zmena je daná (uzavretým) intervalom pohárov. V tomto intervale sa objaví gulička pod každým pohárom, kde sa nenachádzala a zmizne spod každého pohára, kde bola. Jednotlivé zmeny na seba postupne naväzujú.

Raz za čas sa ťa Mišof opýta otázku: Aká je dĺžka najdlhšej (nesúvislej) podpostupnosti, kde na začiatku tejto podpostupnosti sú prázdne poháre a na konci poháre s guličkou? Presnejšie, po žiadnom pohári, pod ktorým je skrytá gulička nemôže v tejto podpostupnosti nasledovať pohár, pod ktorým gulička nie je.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 300\,000\)) – počet pohárov v postupnosti.

V druhom riadku je reťazec znakov 0 a 1, kde 0 reprezentuje pohár, pod ktorým sa gulička nenachádza, a 1 reprezentuje pohár so skrytou guličkou. Tento reťazec určuje začiatočné rozmiestnenie guličiek.

V treťom riadku je číslo \(q\) (\(1 \leq q \leq 300\,000\)) – počet udalostí.

Nasleduje \(q\) riadkov popisujúcich jednotlivé udalosti. Ak sa v riadku nachádza iba jediný znak 1, znamená to, že Mišof sa pýta otázku na aktuálny stav pohárov a guličiek. Ak riadok začína znakom 2, znamená to zmenu intervalu, ktorý je definovaný nasledujúcimi dvoma číslami \(x_i\) a \(y_i\) (\(1 \leq x_i,y_i \leq n\)) na riadku. Prvé číslo je začiatok a druhé číslo je koniec daného intervalu.

Úloha má osem testovacích sád. V prvých piatich z nich platí, že \(n\cdot q \leq 1\,000\,000\). Navyše, v každej párnej sade platí, že \(x_i=y_i\).

Formát výstupu

Pre každú Mišofovu otázku, udalosť 1, vypíšte jedno číslo – dĺžku najdlhšej podpostupnosti pohárov, kde sa všetky poháre, pod ktorými nie je gulička, nachádzajú pred všetkými pohármi, pod ktorými gulička je.

Príklad

Input:

5
00001
6
1
2 1 2
1
2 1 1
2 4 4
1

Output:

5
3
4

V prvej otázke je správna odpoveď celá postupnosť. Po prvej zmene vyzerá celá postupnosť 11001. V tomto prípade jedna so správnych podpostupností pozostáva iba z jednotiek. Na konci dostaneme 01011 a do výsledku vyberiem obe nuly a posledné dve jednotky.