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操作，输出中位数。