Median Finder in a Data Stream

Implement a data structure that efficiently supports adding integers and retrieving the median of the numbers seen so far. The median is defined as follows:

If the sequence has an odd number of elements, the median is the middle element. If the sequence has an even number of elements, the median is given by the formula: \(\frac{a+b}{2}\), where \(a\) and \(b\) are the two middle elements when the sequence is sorted.

You will be given a sequence of commands. Each command is either an addition operation or a query for the current median. When a query is made, output the median of all numbers added so far.

The data structure must support negative values and large numbers as well.

inputFormat

The first line contains a single integer \(n\) representing the number of commands.

Each of the next \(n\) lines is in one of the following two formats:

• a x - where x is an integer to add to the data structure.
• m - a query command that requires you to output the current median.

It is guaranteed that a median query will only be issued after at least one addition.

outputFormat

For each query command (m), output the current median on its own line. If the median is an integer, output it as an integer; if it is not, output it as a decimal number.

## sample

6
a 1
m
a 2
m
a 3
m

1
1.5
2

</p>