KPI

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

你工作以后, KPI 就是你的全部了. 我开发了一个服务,取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录,有时我想知道当前管道内请求的重要值得中间值。

Input

有大约100组数据。

每组数据第一行有一个$n (1 \leq n \leq 10000)$,代表服务记录数。

接下来有n行,每一行有3种形式
  "in x": 代表重要值为$x (0 \leq x \leq 10^9)$的请求被推进管道。
  "out": 代表服务拉取了管道头部的请求。
  "query: 代表我想知道当前管道内请求重要值的中间值. 那就是说,如果当前管道内有m条请求, 我想知道,升序排序后第$floor(m/2)+1_{th}$ 条请求的重要值.

为了让题目简单,所有的x都不同,并且如果管道内没有值,就不会有"out"和"query"操作。

Output

对于每组数据,先输出一行

Case #i:
然后每一次"query",输出当前管道内重要值的中间值。

Sample Input

6 in 874 query out in 24622 in 12194 query

Sample Output

Case #1: 874 24622

Hint

hujie

Source

2015年百度之星程序设计大赛 - 初赛(1)

提交代码