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:

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

Poprawną odpowiedzią jest wyjście:

8
10
11
10
9
12
11
13
14

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 :