Dynamic Median Finder

You are given Q queries to operate on a dynamic data structure. There are two kinds of queries:

1. add x: Insert the integer x into the data structure.
2. median: Output the current median of the numbers.

The median is defined as follows:

• If there is an odd number of elements, the median is the middle element after sorting them.
• If there is an even number of elements, the median is the average of the two middle elements. In mathematical terms, if the two middle numbers are \(x\) and \(y\), then the median is \(\frac{x+y}{2}\).

Your task is to process the queries and, for each median query, output the median on a new line. Note that the output should be exactly as computed (an integer if the median is whole, or a decimal if necessary).

inputFormat

The first line of the input contains an integer Q representing the number of queries. Each of the following Q lines contains one query in one of the following two formats:

• add x where x is an integer.
• median

It is guaranteed that there will be at least one number in the data structure when a median query is made.

outputFormat

For each median query, output the median of the current data set on a separate line. For even numbers of elements, output the average in decimal format.

## sample

6
add 1
median
add 2
median
add 3
median

1
1.5
2

</p>