4. Stovky programátorov

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

Táto úloha je o dátovej štruktúre - Halda. Ak nevieš čo Halda je, môžeš si o nej viac prečítať v študíjnom texte o Halde.

Po tom ako v Krtkove požiadali o pomoc s naprogramovaním čakárne na očkovanie, začali sa programátori a programátorky zo širokého okolia predbiehať, kto túto čakáreň naprogramuje. Keďže čakáreň môže byť iba jedna, musia sa rozhodnúť, kto z nich ju má naprogramovať. To však nie je jednoduché, keďže takýto človek musí mať dostatok skúseností, no zároveň nemôže mať príliš veľa skúseností, lebo potom by cena systému prekročila rozpočet Krtkova.

Úloha

Postupne budú prichádzať ponuky od programátorov a programátoriek s rôznym počtom skúseností. Vašou úlohou bude po každej ponuke zistiť, koľko skúseností má vhodný kandidát. Vhodný kandidát je ten, ktorý má stredne veľa skúseností. To znamená, že polovica kandidátov je horšia a polovica lepšia. Presnejšie sa tejto strednej hodnote hovorí medián. Formálne, medián \(M\) prvkov je taký prvok, ktorý je po utriedení vzostupne na \(\lceil M/2 \rceil\)-tom¹ mieste.

Formát vstupu

Na prvom riadku vstupu je jedno číslo \(1 \leq n \leq 10^5\) - počet programátorov. Na nasledujúcich \(n\) riadkoch sa nachádza vždy jedno číslo, \(0 \leq s_i < 10^9\), počet skúseností programátorov v poradí, v ktorom sa ponúkajú naprogramovať čakáreň.

Formát výstupu

Vypíšte \(n\) riadkov, v \(i\)-tom počet skúseností vhodného kandidáta po \(i\) ponukách.

Príklad

Input:

10
158
182
112
92
52
201
193
167
177
167

Output:

158
158
158
112
112
112
158
158
167
167

Input:

10
83
36
16
58
65
80
52
83
73
71

Output:

83
36
36
36
58
58
58
58
65
65