Problem G
Mette

Mette søger midten. I sit daglige arbejde konfronteres hun med en stadig strøm af nye værdier. Derfor må hun sommetider opdatere hvilken værdi, der er mest i midten.

Nærmere betegnet vil Mette holde fast ved medianen $m$ af $n$ forskellige værdier. Medianen er den værdi, der deler de andre værdier i to lige store mængder. Helt præcist gælder der, at medianen $m$ er den værdi, som er større end $\frac12(n-1)$ værdier og mindre end $\frac12(n-1)$ værdier. Medianen af $(1, 10, 2)$ er $2$.

Når der kommer nye par af værdier, skal Mette opdatere medianen. Hvis de nye værdier for eksempel er $8$ og $1000$, skal Mette nu forholde sig til $(1,10,2, 8,1000)$, og den nye median er derfor $8$. Hvis derefter $7$ og $21$ dukker op, er værdierne $(1,10,2,8,1000,7,21)$; den nye median er dog stadig $8$:

Input

På første linje står antallet $n$ af værdier. Der gælder, at $n$ er ulige og $3\leq n\leq 49\, 999$. På næste linje står de tre første værdier $v_1,v_2,v_3$. På hver af de følgende $\frac12(n-1)-1$ linjer står to nye værdier: først $v_4$ og $v_5$, så $v_6$ og $v_7$, osv. Sidste linje indeholder $v_{n-1}$ og $v_ n$. Alle værdier $v_1,\ldots , v_ n$ er forskellige, og der gælder $0\leq v_ i\leq 10^6$ for alle $1\leq i\leq n$.

Output

TODO: wordsmithing Skriv $\frac12(n-1)$ linjer. Den $i$te linje skal være medianen af $(v_1,\ldots , v_{2i+1})$ for $1\leq i \leq \frac12(n-1)$.

7
1 10 2
8 1000
7 21

2
8
8

3
33 4 5

5