Programowanie dla maturzystów

Niech dany będzie ciąg liczb całkowitych. Medianą ciągu nazywamy liczbę stojącą w środku posortowanej wersji tego ciągu. Jeśli ciąg zawiera parzystą ilość elementów n, to przyjmuje się, że ciąg ma dwie mediany na pozycjach n div 2 oraz (n div 2)+1. My przyjmiemy, że mediana jest jedna i znajduje się w posortowanym ciągu na miejscu n div 2 dla ciągu o parzystej długości lub na miejscu (n div 2)+1 dla ciągu o nieparzystej długości.

Napisz program, który dla podanego ciągu wypisze miedanę tego ciągu.

Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu 1..80000 - ilość liczb ciągu. W każdym z kolejnych n wierszy zapisano jedną liczbę całkowitą z zakresu 1..4*10⁶ - wyrazy ciągu.

W każdym z kolejnych n wierszy zapisano liczbę całkowitą x z zakresu 1..4*10⁶.

Dla każdej wczytanej liczby x należy wypisać aktualną medianę m ciągu, usunąć medianę m z ciągu liczbowego, po czym dodać do tego ciągu liczbę x.
Możesz założyć, że w każdym momencie działania programu wszystkie elementy ciągu są różne, aczkolwiek może się zdarzyć, że wczytana liczba x jest aktualną medianą ciągu.

Dla danych podanych na wejściu:

5
7
12
18
9
14
8
11
12
2
12

Poprawną odpowiedzią jest wyjście:

12
9
11
12
8

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.5 s
Limit pamięci      : 96 MB
Słowa niedozwolone :