Coding is the closest thing we have to superpower !

3700 : 线段树-队列查询
描述

有一个队列,现在对它进行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
标签
语言:
主题: