Running Median

You are given a series of operations to perform on a data structure that maintains a set of integers. The operations are:

• a x: Add the integer x to the data structure.
• m: Query the median of the numbers in the data structure.

The median is defined as follows:

• If the number of elements is odd, the median is the middle element.
• If the number of elements is even, the median is the average of the two middle elements, i.e., \(\frac{a+b}{2}\), where \(a\) and \(b\) are the two middle numbers.

Input is read from standard input and output is produced to standard output. Each query operation m should output the current median on a new line. It is guaranteed that there will be at least one element in the data structure when a median query is made.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10⁵), representing the number of operations. Each of the next n lines contains one operation. An operation is either in the form of "a x" (where x is an integer) or "m" to query the median.

outputFormat

For each median query operation (m), output the median of the numbers added so far. Each output should be on a separate line. If the median is fractional, print the decimal value (for example, 1.5).

3
a 1
a 2
m

1.5