Median Finder

You are required to implement a data structure that supports adding numbers and finding the median of all the numbers added so far. The data structure should efficiently maintain the stream of numbers such that the median can be computed in O(1) time after each addition (amortized).

The median of a list of numbers is the middle element when the list is sorted. More formally, if the numbers are sorted, and there are n numbers, then the median is defined as follows: \[ median = \begin{cases} a_{\frac{n+1}{2}} & \text{if } n \text{ is odd,}\\[5mm] \frac{a_{\frac{n}{2}} + a_{\frac{n}{2}+1}}{2} & \text{if } n \text{ is even.} \end{cases} \]

You will process a series of commands provided via standard input. Each command is one of the following:

• a x: Add the integer x to the data structure.
• m: Print the current median. The median must be printed as a floating-point number with exactly one digit after the decimal point.

Assume that the input is valid and that the "m" command will only be issued when there is at least one number already added.

inputFormat

The first line contains an integer Q representing the number of operations.

Each of the following Q lines contains an operation in one of the formats below:

• a x: where x is an integer to be added.
• m: which indicates that you need to output the current median.

All input is provided via stdin.

outputFormat

For each "m" operation, output the current median as a float with one decimal place. Each median should be printed on a new line. All output is through stdout.

## sample

6
a 1
m
a 2
m
a 3
m

1.0
1.5
2.0

</p>