Dynamic Median Data Structure

You are given a task to design a data structure that supports three operations on a sequence of integers:

• insert x: Insert the integer x into the sequence.
• remove x: Remove one occurrence of integer x from the sequence if it exists.
• get_median: Query the median of the current sequence.

The median is defined as follows:

• If the number of elements is odd, the median is the middle element when the sequence is sorted.
• If the number of elements is even, the median is \(\frac{a+b}{2}\), where \(a\) and \(b\) are the two middle numbers after sorting.
• If the sequence is empty, output Empty.
</p>

Operations are provided via standard input; for each get_median operation, output the result on a new line.

inputFormat

The first line contains an integer \(N\) representing the number of operations.

Each of the next \(N\) lines contains one of the operations in one of the following formats:

• insert x
• remove x
• get_median

Input is read from standard input (stdin).

outputFormat

For every get_median operation, output the median value on its own line. If the sequence is empty when a get_median operation is executed, output Empty.

Output is written to standard output (stdout).

## sample

6
insert 1
insert 3
get_median
remove 1
get_median
insert 1

2
3

</p>