4. Skriňa plná tričiek

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na [email protected]

Jeden z príznakov toho, že chodíte na veľa informatických súťaží, je, že sa vám začnú hromadiť tričká. A Žabovi sa mu ich za tie roky nahromadilo vskutku neúrekom. Teraz ich má uložené v skrini na jednej veľkej kope. Problémom ale je, že Žaba nemá rád zmenu. Keď si teda ráno vyberá, ktoré tričko si dá na seba, zoberie vždy to, čo je navrchu. A večer ho dá do svojej ultramodernej práčky a sušičky v jednom, ktorá mu ho expresne operie a on si ho opäť položí na vrch kopy.

Lucka sa už nemohla pozerať na to, ako Žaba chodí stále v tom istom tričku. Ráno mu preto prikázala, aby si obliekol tričko, ktoré mal na sebe oblečené najmenší počet krát. A keďže takých bolo v kope viacero, zobral to, ktoré bolo najvyššie (t.j. najbližšie pri vrchu). Svoje ďalšie zvyky však Žaba nezmenil – keď večer prišiel domov, tričko opral a hodil na vrch kopy. A tak sa po pár dňoch aj toto nové tričko stalo okukaným.

Lucka mu preto vždy raz za čas povedala, aby si zobral nové tričko a Žaba jej želanie naplnil – teda zakaždým z kopy vytiahol tričko, ktoré mal na sebe dovtedy oblečené najmenejkrát (a v prípade rovnosti to z nich, ktoré bolo nabližšie k vrchu kopy). A keď mu nič nepovedala, tak použil svoj starý prístup a proste zobral tričko, ktoré bolo navrchu. Lucka má teraz problém sa k Žabovi zladiť, preto by potrebovala pomôcť. Vedeli by ste jej povedať, ktoré tričko bude mať Žaba kedy oblečené?

Úloha

Žaba má \(n\) tričiek. Všetky tričká sú uložené na jednej veľkej kope, postupne jedno na druhom. Na začiatku sú očíslované od 1 po \(n\) v poradí zhora nadol – teda tričko 1 je na vrchu kopy, pod ním je tričko 2, a tak ďalej, až po tričko \(n\) úplne na spodku. Pre každé tričko poznáte hodnotu \(t_i\), ktorá označuje, koľkokrát ho už Žaba mal oblečené.

Vašou úlohou bude pre nasledujúcich \(q\) dní zistiť, ktoré tričko bude mať Žaba oblečené. Pritom viete, či si v daný deň zoberie tričko z vrchu kopy, alebo nájde najvyššie tričko v kope, ktoré mal oblečené najmenší počet krát.

Pamätajte na to, že po každom dni si Žaba dané tričko vyperie a položí na vrch kopy, pričom počet nosení tohto trička sa zvýši o jedna.

Formát vstupu

Na prvom riadku vstupu sú dve čísla \(n\) a \(q\) – počet tričiek na kope a počet najbližších dní, ktoré Lucku zaujímajú.

Na druhom riadku vstupu je \(n\) medzerami oddelených čísel \(t_1, t_2 \dots t_n\). Hodnota \(t_i\) označuje, koľkokrát mal Žaba už oblečené tričko \(i\).

Nasleduje \(q\) riadkov. Na každom z nich je jeden znak – Z alebo L – určujúci rozhodnutie, ktoré v daný deň Žaba spraví. Ak je na vstupe Z, Žaba si zoberie najvrchnejšie tričko kopy. Ak je na vstupe L, vyberie si to tričko, ktoré mal na sebe najmenší počet krát. V prípade, že je takýchto tričiek viac, vyberie si to, ktoré je v kope najvyššíe.

Formát výstupu

Pre každý z \(q\) dní vypíšte na samostatný riadok číslo trička, ktoré si v ten deň Žaba oblečie.

Hodnotenie

Vaše riešenie bude testované iba na 5 rôznych vstupoch. Za každý vstup, na ktorý odpovie váš program správne získate 3 body.

V prvých dvoch vstupoch platí, že \(n = 1\,000\) a \(q = 5\,000\).

V zvyšných troch je \(n = 100\,000\) a \(q = 500\,000\).

V treťom vstupe môžete navyše predpokladať, že počas všetkých dní platí, že rozdiel najväčšieho a najmenšieho počtu nosení niektorého trička nepresiahne 2.

Vo všetkých vstupoch platí, že začiatočné hodnoty nosení \(t_i\) nepresiahnu \(1\,000\,000\).

Príklady

Input:

5 7
2 3 2 4 2
Z
L
Z
L
L
Z
L

Output:

1
3
3
5
5
5
1

Prvý deň si Žaba oblečie tričko z vrchu kopy, teda tričko s číslom 1. Na druhý deň si má obliecť tričko s najmenším počtom nosení. Také sú v kope dve, číslo 3 a 5, vyššie z nich je však tričko 3, preto si ho oblečie a dá na vrch kopy. Tretí deň opäť zoberie toto tričko zvrchu kopy, tričko číslo 3 teda bolo nosené už štyri dni. Na štvrtý deň je tričko s najmenším počtom nosení tričko číslo 5, Žaba si ho preto oblečie. Piaty deň si má opäť vybrať tričko, ktoré mal na sebe najmenší počet krát. V tomto prípade má na výber tričká 1, 2 a 5. Najvyššie z nich, a zrovna na vrchu kopy, je tričko číslo 5, preto si ho oblečie. Na šiesty deň svoju voľbu zopakuje a v posledný deň si vyberie vyššie z dvoch tričiek, ktoré mal na sebe iba trikrát – tričko číslo 1.