AlgoLiga 2018

W końcu nadszedł najlepszy dla Bajteusza okres w roku - sezon na Ciągówki! Nasz bohater wprost ubóstwia te smakowite owoce. Już na samą myśl cieknie mu ślinka.

Nie chcąc wydawać niepotrzebnie pieniędzy, jako oszczędny student postanowił sam zebrać trochę swojego ulubionego przysmaku. Wyruszył więc do lasu z pustym koszem i zaczął ciągówkobranie. Raz na jakiś czas Bajteusz nie może wytrzymać i zjada jakąś ciągówkę. Nie szczędząc sobie przyjemności zawsze wybiera on najsmaczniejszy okaz. Wybranie takowego jest dosyć proste, jako że każdy owoc ma na sobie określoną ilość plamek odpowiadającą wiekowi (w dniach) danej ciągówki, a najlepiej smakują nie za stare, ale jednak dojrzałe owoce. Innymi słowy Bajteusz wybiera zawsze środkową względem wieku ciągówkę i ją natychmiast zjada (jeżeli są dwa owoce o środkowym wieku, to nasz bohater wybiera starszy).

Pomóż Bajteuszowi wybrać, którą ciągówkę powinien skonsumować.

Wejście

Wejście składa się z nieokreślonej liczby wierszy (nie więcej niż 600 000). W każdym wierszu znajduje się znak zapytania albo liczba z przedziału [0, 10⁹] oznaczająca wiek nowej ciągówki, którą zerwał Bajteusz.

Wyjście

Dla każdego znaku zapytania należy wypisać w oddzielnej linii wiek ciągówki, którą w danej chwili spożyje Bajteusz.

Przykład

Wejście:
1
2
2
3
?
4
?
?
?
?

Wyjście:
2
3
2
4
1