Streaming Median

You are given a stream of integers. Your task is to calculate the running median as each integer from the stream is processed. The median \(m\) of a list of numbers sorted in non-decreasing order is defined as follows:

$$ m=\begin{cases} a_{\frac{n+1}{2}} & \text{if } n \text{ is odd}\\ \frac{a_{\frac{n}{2}}+a_{\frac{n}{2}+1}}{2} & \text{if } n \text{ is even} \end{cases} $$

After receiving each new number, output the current median. All inputs will be read from standard input and the results should be written to standard output.

inputFormat

The first line contains an integer (N) (where (0 \le N \le 10^5)) representing the number of elements in the stream. The second line contains (N) space-separated integers.

outputFormat

Output the running medians separated by a single space. For each new number in the stream, print the median of all numbers seen so far.## sample

7
2 1 5 7 2 0 5

2 1.5 2 3.5 2 2 2