C - Čínsky výškomer

Čínsky štatistický úrad to vôbec nemá jednoduché. Isto uznáte, že akékoľvek štatistické zisťovanie o 1.38 miliarde obyvateľov Číny dá zabrať. Vedenie Číny sa rozhodlo preskúmať rôzne fyzické parametre obyvateľstva. Keďže jedným zo skúmaných parametrov je výška, štatistici vytvorili špeciálny automatický výškomer, ktorý im pri analyzovaní výšok obyvateľov pomôže. Tento výškomer meria výšku s presnosťou na centimetre. Spočiatku bolo v pláne zisťovať len priemernú výšku (na to stačí poznať súčet výšok a ich počet) a preto bol výškomer vybavený len malou pamäťou. Keď už boli všetky výškomery pre štatistikov vyrobené, prišla požiadavka, aby výškomer okrem priemernej výšky zrátal aj medián z nameraných výšok. Firmware výškomera treba teraz preprogramovať tak, aby uvedený medián nejako zrátal pri rešpektovaní pamäťových obmedzení.

Čo je medián? Wikipédia hovorí: Medián alebo prostredná hodnota (znaku) je hodnota, ktorá rozdeľuje postupnosť podľa veľkosti zoradených výsledkov na dve rovnako početné polovice. V štatistike patrí medzi stredné hodnoty. Platí, že najmenej 50 % hodnôt je nižších alebo sa rovná a najmenej 50 % hodnôt je vyšších alebo sa rovná mediánu. Na nájdenie mediánu daného súboru stačí hodnoty zoradiť podľa veľkosti a zobrať hodnotu, ktorá sa nachádza v strede zoznamu. Keď má súbor párny počet prvkov, je viacero možností ako definovať medián. Čínsky štatistický úrad sa z PR dôvodov rozhodol za medián sa označiť väčšiu z hodnôt na miestach n/2 a n/2+1 (pri indexovaní hodnôt od 1).

Úloha

Vytvorte program, ktorý prečíta namerané výšky a vypočíta medián týchto výšok pri rešpektovaní zadaných pamäťových obmedzení.

Vstup

Prvý riadok vstupu obsahuje celé číslo n (1 ≤ N ≤ 10⁷) určujúce počet nameraných výšok. V nasledujúcich N riadkoch je v každom riadku jedna nameraná výška. Vzhľadom na fyziologické obmedzenia platí, že výška je celé číslo V, pre ktoré platí 10 ≤ V ≤ 300.

Výstup

Výstupom je medián z nameraných výšok.

Príklady

Vstup:

10
190
201
232
103
205
183
193
102
157
226

Výstup:

193

Vstup:

11
132
225
122
200
205
225
172
116
191
137
163

Výstup:

172

Poznámka

V prípade implementácie riešenia v jazyku Java, použite rýchlejšie načítavanie cez BufferedReader: Poznámky k jazyku Java