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:

13
1
17
7
4
10
16
13
3
2
6
14
9
5
12
11
19
15
12
10
12
18
10
8
9
9
10

Poprawną odpowiedzią jest wyjście:

7
9
10
11
12
12
10
12
13
10
8
9
9

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 :