题目内容

你需要设计一个数据结构，不断接收整数数据流，并且能在任意时刻都能查询当前所有已接收整数的中位数。

中位数的含义如下：将当前所有元素按非递减顺序排列后，如果元素个数是奇数，则中位数是正中间的那个数；如果元素个数是偶数，则中位数是中间两个数的平均值。例如，[2,3,4] 的中位数是 3，[2,3] 的中位数是 (2 + 3) / 2 = 2.5。

需要实现名为 MedianFinder 的类，它包含以下方法：

• MedianFinder()：初始化数据结构。
• addNum(int num)：将整数 num 添加到当前数据流中。
• findMedian()：返回目前所有已添加元素的中位数。只要返回结果与真实中位数的误差不超过 $10^{-5}$，就会被判定为正确。

约束条件：

• 每次调用 addNum 时，整数 num 满足 $-10^5 \le num \le 10^5$。
• 每次调用 findMedian 时，数据结构中至少已经添加了一个元素。
• addNum 和 findMedian 两种操作的总调用次数不超过 $5 \times 10^4$。

输入描述

第一行包含一个整数 q，表示操作的总次数。

接下来 q 行，每行描述一个操作：

• 若为 add x，表示向数据流中添加整数 x；
• 若为 median，表示查询当前所有元素的中位数。

输出描述

对于每个 median 操作，输出一行当前的中位数，结果保留 1 位小数。

样例1

输入

4
add -100000
median
add 100000
median

输出

-100000.0
0.0

说明

第一次 add 后，当前数据流只有 -100000，因此中位数就是 -100000，输出 -100000.0。

第二次 add 后，当前数据流为 $[-100000, 100000]$，元素个数为 2，中位数为两个数的平均值 $\frac{-100000 + 100000}{2} = 0.0$，因此输出 0.0。

样例2

输入

7
add 10
add 20
median
add 5
median
add 100
median

输出

15.0
10.0
15.0

说明

前两次 add 后，数据流为 $[10, 20]$，中位数是 $\frac{10+20}{2}=15.0$，输出 15.0。

加入 5 后，排序为 $[5, 10, 20]$，元素个数为 3，正中间是 10，输出 10.0。

再加入 100 后，排序为 $[5, 10, 20, 100]$，元素个数为 4，中间两个数为 10 和 20，平均值 $\frac{10+20}{2}=15.0$，输出 15.0。

样例3

输入

7
add -5
add -10
median
add -3
median
add -1
median

输出

-7.5
-5.0
-4.0

说明

前两次 add 后，排序为 $[-10, -5]$，中位数为 $\frac{-10 + (-5)}{2} = -7.5$，输出 -7.5。

加入 -3 后，排序为 $[-10, -5, -3]$，元素个数为 3，正中间是 -5，输出 -5.0。

再加入 -1 后，排序为 $[-10, -5, -3, -1]$，元素个数为 4，中间两个数为 -5 和 -3，平均值 $\frac{-5 + (-3)}{2} = -4.0$，输出 -4.0。