Running Median

You are given an array of integers. Your task is to compute the running median after each new element is added to the array. The median after insertion is defined as follows:

• If the number of elements is odd, the median is the middle element after the array is sorted.
• If the number of elements is even, the median is \( \frac{a_{\frac{n}{2}}+a_{\frac{n}{2}+1}}{2} \) (using 1-indexed notation) after the array is sorted.

You need to read the input from standard input and output the sequence of medians, each represented as a float with one decimal place, separated by a space.

Note: Ensure that your solution can handle various orders of input numbers efficiently.

inputFormat

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

Example:

6
12 4 5 3 8 7

outputFormat

Output a single line containing \( n \) medians corresponding to the running median after each insertion. Each median should be represented as a float with one decimal place, separated by a space.

Example:

12.0 8.0 5.0 4.5 5.0 6.0

## sample

6
12 4 5 3 8 7

12.0 8.0 5.0 4.5 5.0 6.0

</p>