4690 - 第十三课:队列查询

有一个队列,现在对它进行n次操作,每次操作可以是下面三种中的一种:

  "in x": 向队列中加入插入一个整数$ x(0 \le x \le 10^9) $。

  "out": 从队列中弹出一个数字。
  "query": 从队列中查询中位数,例如队列中有m个数字,则中位数是,升序排序后第$ floor(\frac{m}{2})+1 $ 个数字。

初始队列为空。

点击队列查看定义

输入

第一行包含一个整数$ n(1 \le n \le 10^5) $。

接下来n行,每行给出一个操作,形式如上所述。

输入保证所有的x都不相同,如果队列为空,则不会有query和out操作。

输出

对于query操作,输出中位数。

样例

输入

6
in 874
query
out
in 24622
in 12194
query

输出

874
24622
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题