Sinulle annetaan taulukko, jossa on $n$ lukua. Ilmoita jokaiselle $k=1,2,\ldots,n$, mikä on taulukon $k$ ensimmäisen luvun mediaani.

Mediaani on keskimmäinen luku, kun luvut on järjestetty pienimmästä suurimpaan. Jos lukujen määrä on parillinen, tulkintana on tässä tehtävässä, että mediaani on keskikohdan vasemmalla puolella oleva luku.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: lukujen määrä.

Tämän jälkeen syötteessä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$.

Tuloste

Tulosta $n$ lukua: halutut mediaanit.

Rajat

• $1 \le n \le 10^5$
• $1 \le x_i \le 10^9$

Esimerkki

Syöte:

5
3 2 5 5 4

Tuloste:

3 2 3 3 4