Balanced Multiset Median Operations

This problem requires you to implement a balanced multiset that supports three types of operations:

• add x: Insert the integer x into the multiset.
• remove x: Remove one occurrence of the integer x from the multiset if present.
• median: Compute and output the median of the multiset.

The median is defined as follows. Suppose the sorted multiset is \(a_1,a_2,\dots,a_n\):

• If \(n\) is odd, the median is \(a_{\frac{n+1}{2}}\).
• If \(n\) is even, the median is \(\left\lfloor\frac{a_{\frac{n}{2}}+a_{\frac{n}{2}+1}}{2}\right\rfloor\) (i.e. the average of the two middle numbers, rounded down).

You will be given a series of operations. For every median operation, output the current median on a new line.

inputFormat

The input is read from standard input. The first line contains an integer N representing the number of operations. Each of the next N lines contains one of the following operations:

• add x — to add an integer x to the multiset.
• remove x — to remove an integer x from the multiset (if it exists).
• median — to query the median of the current multiset.

outputFormat

For each median operation, output the median in a separate line. There should be no extra spaces or blank lines.

## sample

8
add 1
add 3
add 4
median
remove 3
median
add 7
median

3
2
4

</p>