Bolo raz jedno mesto. V tom meste bola nemocnica. V tej nemocnici boli pacienti a bolo ich dosť veľa. No prišiel Jurko Štatista a začal robiť štatistiku pacientov. Keď prišiel pacient do nemocnice, zapísal si jeho meno, rok narodenia, hmotnosť, výšku, veľkosť palca, lakťa a nechcite vedieť, čoho ešte všetkého. No nebol by to náš Jurko, keby nechcel všetky štatistické veci rátať a vyvodzovať z toho dôsledky. I rozhodol sa on rátať medián výšok pacientov. Rozmýšľa a rozmýšľa, ale predsa len je to štatista a nie programátor.
Na vstupe je číslo $1 \leq N \leq 10^5$ a za ním postupnosť $0 \leq d_i < 10^9$ výšok pacientov v poradí, ako prichádzajú do nemocnice. Vašou úlohou je pre každého prichádzajúceho pacienta povedať, aký je medián výšok pacientov, ktorý do nemocnice prišli dovtedy (vrátane neho). Medián $M$ prvkov je taký prvok, ktorý by bol po utriedení vzostupne na $\lceil M/2 \rceil$-tom mieste.
10
158 182 112 92 52 201 193 167 177 167
158 158 158 112 112 112 158 158 167 167
10
83 36 16 58 65 80 52 83 73 71
83 36 36 36 58 58 58 58 65 65
2
1000 100
1000 100