Coding is the closest thing we have to superpower !
描述
有一个队列,现在对它进行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
标签