Running Median

You are given a sequence of integers, and you need to compute the running median of the sequence. After each new number is added to the sequence, output the median of all numbers seen so far.

The median is defined as follows:

• If the number of elements is odd, the median is the middle element.
• If the number of elements is even, the median is given by \(\frac{a+b}{2}\), where \(a\) and \(b\) are the two middle elements (in sorted order).

For example, consider the sequence: [2, 1, 5, 7, 2, 0, 5]. The running medians are: [2, 1.5, 2, 3.5, 2, 2, 2].

Your task is to implement a solution that reads input from stdin and writes the output to stdout following the format described below.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains an integer \(n\) — the number of elements in the sequence.
2. The second line contains \(n\) space-separated integers.

outputFormat

Output the running median after each insertion in one line. The medians should be separated by a single space. If the median is an integer, output it without a decimal point; otherwise, output it as a floating point number.

7
2 1 5 7 2 0 5

2 1.5 2 3.5 2 2 2