| 问题描述 |
|---|
一家公司有 n 名员工，每个员工有一个工资 x，作为这家公司的人事，你负责 招聘新员工 以及向老板 汇报工资中位数，共计 m 次。 |
| 输入描述 |
第一行包含两个正整数 n 和 m 分别表示初始时公司的人数和操作的数量。（1 <= n，m <= 2e5） 接下来是 n 个正整数 x 分别表示初始时公司每名员工的工资。（1 <= x <= 1e9） 最后 m 行，每行表示一个操作： Query：输出当前所有员工的工资中位数。如果员工数量为偶数，则取最中间两个人工资的平均数（向下取整）。 New x：公司招聘了一个工资为 x 的新员工。（1 <= x <= 1e9） |
| 输出描述 |
针对每个 Query 操作，输出所有员工的工资中位数，然后换行。 |
| 样例输入复制样例 |
3 3 10 20 30 Query New 15 Query |
| 样例输出 |
20 17 |
| 提示说明 |
(15 + 20) / 2 = 17.5 => 17 |
| 相关 |