Running Median

You are given a stream of n integers. After each integer is added, your task is to compute the median of the numbers seen so far. The median of a set of numbers is defined as:

\( \text{median} = \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} \)

where the sequence \( a_1 \leq a_2 \leq \cdots \leq a_n \) is the sorted order of the numbers received so far. Output the median after each insertion, formatted to one decimal place.

inputFormat

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

outputFormat

Output \( n \) lines, each containing the median of the stream after each integer is added. The median must be output as a floating point value with one decimal point.

## sample

5
10 20 30 40 50

10.0
15.0
20.0
25.0
30.0

</p>