MultiSet Median Query

You are given a series of operations to perform on a multiset. The multiset supports the following operations:

• insert x: Insert the integer x into the multiset.
• remove x: Remove one occurrence of the integer x from the multiset (if it exists).
• get_median: Output the median of the multiset. When the multiset contains an even number of elements, the median is defined as the lower of the two middle elements. In other words, if the sorted order is \(a_1, a_2, \dots, a_n\), then the median is given by: \[ \text{median} = \begin{cases} a_{\frac{n+1}{2}} & \text{if } n \text{ is odd},\\ a_{\frac{n}{2}} & \text{if } n \text{ is even}. \end{cases} \]

You need to implement these operations so that each get_median operation prints the current median of the multiset. All operations will be given in order, and you should process them accordingly.

inputFormat

The first line of input contains an integer T representing the number of operations. Each of the next T lines contains one of the three operations:

• insert x
• remove x
• get_median

Input is given via standard input (stdin).

outputFormat

For each get_median operation, output the median of the multiset on a new line. Output is produced on standard output (stdout).

## sample

3
insert 1
insert 5
get_median

1

</p>