Ujo Fero prevádzkuje netradičný obchod s vianočnými stromčekmi. Keďže jeho stromčeky sú obrovské a ťažké, nemôže ich len tak nechať voľne stáť na zemi. Namiesto toho ich má zavesené na jednej dlhej, úzkej koľajnici pod stropom.
Táto konštrukcia má však jeden háčik. Nové stromčeky sa dajú na koľajnicu pridávať len z dvoch strán – buď ich ujo Fero zavesí na úplný začiatok (zľava), alebo na úplný koniec (sprava). Rovnaké obmedzenie platí aj pre nákup. Keď príde zákazník, ujo Fero dokáže zvesiť iba tie stromčeky, ktoré sú momentálne na krajoch koľajnice, pretože k ostatným sa uprostred radu nedostane.
Keď do obchodu vstúpi zákazník, pozrie sa na stromček úplne vľavo a stromček úplne vpravo. Porovná ich a kúpi si ten, ktorý je krajší (má vyššiu hodnotu krásy). Ak by mali oba krajné stromčeky rovnakú krásu, zákazník uprednostní ten vľavo, aby ujo Fero nemusel chodiť na druhý koniec haly. Vybraný stromček sa následne z koľajnice zvesí a odovzdá zákazníkovi.
Ujo Fero ale odišiel konferenciu KSP1 a požiadal vás, aby ste ho zastúpili.
Postupne dostávate $q$ požiadaviek troch typov:
Simulujte tieto operácie.
Na prvom riadku je čislo $q$ - počet požiadaviek, $0 < q <= 10^7$.
Nasleduje $q$ riadkov:
> k - z ľava pribudol stromček s krásou $k$< k - z prava pribudol stromček s krásou $k$? - vyberieme krajší z krajných stromčekov (alebo ľavý)Pre krásu platí, že $0 <= k <= 10^9$, kde krajší je stromček s vyššou hodnotou krásy.
Pre každú požiadavku ? vypíšte hodnotu krásy stromčeka, ktorý ste predali.
3
< 2
> 4
?
4
Stav koľajnice je postupne 2, 4 2, 2.
8
> 3
< 5
> 2
?
> 4
> 3
?
?
5
3
4
Stav koľajnice je postupne 3, 3 5, 2 3 5, 2 3, 4 2 3, 3 4 2 3, 4 2 3, 2 3
Klubu Stromčekových Predajcov ↩