Runda 3: Kolejarz Paweł

Limit czasowy: 10 sekund
Limit pamięciowy: 64 MB

Pan Paweł uwielbiał pociągi jeszcze zanim nauczył się czytać i pisać. Z czasem dziecinne zainteresowanie przerodziło się w pasję, a potem w zawód. Mówiąc krótko - pan Paweł jest kolejarzem na stacji załadunkowej w małej podwrocławskiej miejscowości.

Stacja pana Pawła ma tylko jedną linię kolejową, na której ruch odbywa się w jedną stronę. Pociągi opuszczają stację w kolejności, w której do niej przyjeżdzają. Życie na stacji płynie wolnym tempem, przez większość dnia nic się tam nie dzieje. Spokój zakłóca tylko od czasu do czasu jedno z trzech wydarzeń:

• przyjazd pociągu o określonej ładowności,
• wyjazd pociągu znajdującego się na stacji, który pojawił się na niej jako pierwszy,
• telefon z centrali.

 
Pan Paweł nie znosi telefonów z centrali, biurokraci zawsze pytają o to samo. Chcąc poznać mniej więcej przeciętną ładowność pociągów na stacji proszą pana Pawła o podanie mediany ładowności pociągów na stacji. To doprowadza naszego bohatera do szewskiej pasji - musi za każdym razem zapisać na kartce wszystkie ładowności, posortować je i wyznaczyć środkową (lub dwie środkowe, jeśli jest ich parzyście wiele). Czy potrafisz pomóc panu Pawłowi pisząc odpowiedni program?

Wejście

W pierwszej linii wejścia znajduje się liczba N (1<=N<=10⁶), oznaczająca liczbę wydarzeń na stacji pana Pawła. W kolejnych N liniach znajdują się opisy wydarzeń. Każdy opis jest postaci:

• "przyjazd X" — oznacza przyjazd na stację pociągu o ładowności X (1<=X<=10⁶),
• "odjazd" — oznacza odjazd kolejnego pociągu.
• "telefon" — oznacza telefon z centrali.

Centrala gwarantuje, że nie będzie dzwonić, kiedy na stacji nie będzie żadnych pociągów. Zdrowy rozsądek gwarantuje, że w takiej sytuacji żaden pociąg ze stacji nie odjedzie. Zakładamy, że na początku na stacji pana Pawła nie ma żadnych pociągów.

Wyjście

Każdemu poleceniu 'telefon' powinna odpowiadać dokładnie jedna (kolejna w porządku zadawania zapytań) linia wyjścia programu. Należy wypisać medianę ładowności pociągów na stacji - jeśli jest ich parzyście wiele, należy wypisać dwie środkowe wartości oddzielone spacją w kolejności niemalejącej.

Przykład

Dla danych wejściowych:

10
przyjazd 1
telefon
odjazd
przyjazd 3
przyjazd 4
telefon
przyjazd 5
telefon
odjazd
telefon

poprawną odpowiedzią jest:

1
3 4
4
4 5