Migrated from Lutece 1339 郭大侠与线上游戏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

曾在网络游戏告白，但对方是假冒女生的人妖，而对此有阴影的郭大侠，坚持把游戏和现实分得清清楚楚。有一天竟被网络游戏中的女玩家告白了，虽然在游戏中接受了亚子的表白而结婚，但仍然不敢确信亚子就是真真正正的女生。终于有一天，卢西安所属四人公会的富豪会长决定举行线下聚会，结果发现四个人居然都是同一所高中的学生，甚至另外三人都是真真正正的可爱女孩子。

郭大侠还没完全接受这个事实时，他们发现亚子居然是重度的现实游戏混淆症患者，不仅在现实生活中用游戏角色名字“卢西安”叫人，还旁若无人黏住英骑身上。为了让亚子能够恢复正常，四人的游戏生活延续至学校。

……

今天，拯救亚子的计划是玩游戏！

这个游戏是这样的~

有一个像队列一样的东西，你可以push一个元素到这个队列的尾部，也可以pop掉这个队列的第一个元素

现在问题来了，这个队列中位数是多少呢？

中位数的定义为该队列升序排序后第k/2+1个的数的值，k为这个队列的大小

Input

第一行一个$n$，表示有n个操作

接下来$n$行为这三个操作之一：

1 x，向这个队列推入一个数x

2，弹出这个队列的第一个数

3，查询这个队列的中位数是多少

$1<=n<=1000000$，保证输入都是在int范围的整数。

保证队列中的每个数都不一样哦~

Output

对于每一个询问输出答案。

保证有解~

Samples

6
1 2
3
1 4
3
2
3

2
4
4

Resources

2016 UESTC Training for Data Structures