Median Set Query Processor

You are given a series of queries that operate on a multiset (a set where duplicate integers are allowed) of integers. There are two types of queries:

1. insert x: Insert the integer $x$ into the set. Duplicates are allowed.
2. median: Print the median of the current set of integers.

The median is defined as follows:

• If the number of elements $n$ is odd, the median is the element in the sorted order at position $\lfloor n/2 \rfloor$ (0-indexed).
• If $n$ is even, the median is the average of the two middle elements. That is, if the sorted order is $a_0, a_1, \ldots, a_{n-1}$, then the median is given by $$\frac{a_{n/2 - 1} + a_{n/2}}{2.0}.$$

You must process the queries in the order they are given. For each query of type "median", output the median formatted to one decimal place.

It is guaranteed that at least one insertion occurs before any median query.

inputFormat

The first line contains an integer $Q$ ($1 \le Q \le 10^5$), the number of queries. Each of the next $Q$ lines contains either a query of the form "insert x", where $x$ is an integer, or the string "median".

outputFormat

For each query of type "median", print the median on a new line, formatted to one decimal place.## sample

7
insert 1
insert 2
median
insert 3
median
insert 4
median

1.5
2.0
2.5