Running Median

You are given a stream of integers. For each new integer in the stream, you must output the median of the list so far. The median is defined as follows:

If \(n\) is odd, the median is the middle element when the stream is sorted. If \(n\) is even, the median is \(\frac{a + b}{2}\), where \(a\) and \(b\) are the two middle elements.

Your task is to implement a program that computes the running median of the input stream.

Example:

Input: 7
       2 1 5 7 2 0 5
Output: 2 1.5 2 3.5 2 2 2

Note that the medians should be computed after reading each number in the given order.

inputFormat

The first line of input contains an integer \(n\) denoting the number of elements in the stream. The second line contains \(n\) space-separated integers representing the stream.

outputFormat

Output a single line containing \(n\) values, where the \(i\)-th value is the median of the first \(i\) numbers in the stream. When the median is not an integer, output it as a floating-point number (e.g., 1.5). Values are separated by a single space.

7
2 1 5 7 2 0 5

2 1.5 2 3.5 2 2 2