Median Finder

You are required to design a data structure that supports the following two operations:

• add X: Add an integer X to the data structure.
• median: Output the median of all the numbers added so far.

The median is defined as follows:

• If the number of elements, \( n \), is odd, then the median is the middle element after sorting.
• If \( n \) is even, then the median is defined as
  \( \frac{a_{n/2} + a_{n/2+1}}{2} \), where \( a_i \) is the \( i^{th} \) smallest element.

Input Format: 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 following forms:

add X
median

Output Format: For each median operation, output the median in a new line. It is guaranteed that there is at least one number in the data structure when a median query is made.

inputFormat

The first line of input is an integer \( Q \) (1 ≤ \( Q \) ≤ 5×10⁴) representing the number of operations. Each of the next \( Q \) lines contains a command:

• add X where \( X \) is an integer such that -10⁵ ≤ \( X \) ≤ 10⁵.
• median indicates a query to find the median of the current list of numbers.

outputFormat

For each median command, print the median on a new line. If the median is an integer, print it without any trailing decimal point; if it is the average of two numbers, print the resulting floating point value.

## sample

6
add 1
median
add 2
median
add 3
median

1
1.5
2

</p>