Running Median

Integers are given one at a time. After each integer is added, output the median of all integers seen so far after sorting them.

If the number of integers seen so far is even, the median is defined as the smaller of the two middle values. Write a program that outputs this value after every input integer.

The first line contains the number of integers N. 1 <= N <= 100,000.

Each of the next N lines contains one integer in order. For every integer x, -10,000 <= x <= 10,000.

Print N lines. On each line, print the median immediately after reading the corresponding integer.