5. Kopa neumytého riadu

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 Liahne (liahen.ksp.sk). Keď budeš riešiť sadu arrays_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 Andrejovi na [email protected]

Dávidovi sa počas skúškového nič nechce. A už vôbec nie umývať taniere. Vždy keď niečo zje, spraví minimum námahy a tanier položí niekam vedľa seba. Občas, keď sa mu už ťažko chodí po izbe, tak nejaké taniere pozbiera a uloží ich na kopu neumytých tanierov. Ešte menej často si povie, že nejaký tanier na kope sa už časom mohol stať toxickým. Kopa neumytých tanierov medzitým poriadne narastie a on sa rozhodne, že problém trochu zmierni a umyje niekoľko najvrchnejších tanierov.

Aby vedel či už taniere treba umývať, tak si pre každý z nich pamätá jedno číslo, ktoré vyjadruje kedy naposledy bol daný tanier umytý. Dávidovi sa však nechce stále premýšľať, či má ísť už umyť taniere a aký tanier v kope je najdlhšie neumytý. Požiadal vás preto, aby ste mu na to napísali program a on už nemusel nad riadom tak intenzívne premýšľať.

Úloha

Vašou úlohou je napísať program, ktorý bude simulovať kopu neumytých tanierov. Program by mal preto vedieť spracovať 3 typy udalostí: 1. Pridanie taniera, ktorý bol naposledy umytý v čase \(x\). 2. Umytie najvrchnejšieho taniera na kope. 3. Nájdenie najtoxickejšieho, teda najdlhšie neumytého, taniera z kopy.

Formát vstupu

Na prvom riadku vstupu je jedno celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)). Potom nasleduje \(n\) riadkov. Na každom riadku sa nachádza popis jedného príkazu. Ako sme spomínali, existujú 3 typy príkazov:

Ak ide o príkaz 1. typu, na riadku sa bude nachádzať reťazec ‘PRIDAJ x’, kde x je celé číslo a platí \(1 \leq x \leq 1\,000\,000\,000\).

Ak ide o príkaz 2. typu, na riadku sa bude nachádzať reťazec ‘UMY’.

Ak ide o príkaz 3. typu, na riadku sa bude nachádzať reťazec ‘NAJSPINAVSI’.

Formát výstupu

Pre každý príkaz 3. typu vypíšte na samostatný riadok výstupu jedno číslo. To hovorí, že najdlhšie neumytý tanier na kope bol umytý naposledy v čase \(x\). Ak sa na kope nenachádza žiadny tanier, vypíšte -1.

Hodnotenie

Vaše riešenie bude testované na 3 sadách. Rôzne sady sa budú líšiť špeciálnymi obmedzeniami:

Príklady

Input:

7
PRIDAJ 30
NAJSPINAVSI
PRIDAJ 20
PRIDAJ 10
NAJSPINAVSI
UMY
NAJSPINAVSI

Output:

30
10
20

Na prvom riadku určíme počet príkazov, ktoré budú nasledovať – 7. Prvý príkaz pridá na kopu jeden tanier, ktorý bol umytý naposledy v čase 30. Keď sa spýtame na najšpinavší tanier v druhom príkaze, na kope sa nachádza jediný tanier s časom 30. Potom pridáme ešte 2 taniere, pričom jeden sa stane najšpinavším, ten je ale v zápätí vybraný a našpinavším sa stáva tanier s číslom 20.

Input:

6
NAJSPINAVSI
PRIDAJ 8
PRIDAJ 10
NAJSPINAVSI
UMY
UMY

Output:

-1
8

Na vstupe je 6 príkazov. Pri prvom príkaze na nájdenie najšpinavšieho taniera nie je žiadny na kope, takže vypíšeme -1. Potom pridáme dva taniere, najšpinavším sa stane tanier, ktorý bol naposledy umytý v čase 8 a potom oba taniere umyjeme.