RMID2 - Running Median Again


Danish has just solved the problem Running Median.

The first line of the problem says "You will be given some integers in non-decreasing order". The problem asks you to report and remove the median of the list every time it is queried.

Having solved this problem, Danish now begins to wonder how to solve the problem if the input is in any order (not necessarily non-decreasing order as mentioned above).

Can you help him?

Your task is to take as input a list of positive integers. Whenever -1 is given as input, you must output the median of the list, and remove it from the list. Take the smaller element as the median in case of even number of elements.

Input

The input contains several test caes.

The first line contains an integer t, the number of test cases.

Each test case has several lines, each containing an integer n (<=10^9) . If n is positive, add it to the list. n=-1 indicates a median query (there will be no median query if the list is empty). The test case is terminated by n=0.

In each test case, there will be upto 10^5 integers to be added to the list, and upto 10^5 median queries.

Output

For each median query as described above, print the median on a new line.

Example

Input:
1
9
10
2
5
1
18
-1
-1
4
3
-1
8
7
-1
0

Output:
5
9
3
7

hide comments
parijat bhatt: 2015-06-25 11:31:17

co-ordinate compression+BIT

Gannu_raj: 2015-06-04 15:15:02

Why it gives me WA ? I using maxheap and minheap .
Am I correct with my concept?

Abhilash: 2015-03-11 15:06:02

Used fast I/O

Praveen Yadav: 2015-03-03 08:14:48

In this example test case
1-denotes no of test case
9
10
2
5
1
18
-1
Now how can be this 5 it should be 2


Reply: The numbers in the list so far are 1,2,5,9,10,18. The median is clearly 5 (take the left element in case of even number of elements).

Last edit: 2015-03-05 15:48:46
Bharath Reddy: 2014-09-27 07:03:23

Used the same solution I wrote for RMID (except for the I/O reading) and got AC here.

joud zouzou: 2014-01-16 12:00:51

Why is the second query's answer is 9?
1 1 2 5 9 10 18
median is 5, delete 5
1 1 2 9 10 18
length is even, take smaller one between (2,9)-> 2


REPLY (Akhilesh):
The first '1' in the input indicates that there is one test case. it is not a part of the list.
1 2 5 9 10 18
Median is 5 -> delete it
1 2 9 10 18
Median is smaller of (9,10) -> so the answer is 9

Last edit: 2014-01-29 13:23:41
­Surendra: 2013-11-08 09:53:39

@Akhilesh : Can there be duplicate elements as well ?

Reply: Yes, there can.

Last edit: 2013-11-08 18:00:34

Added by:Akhilesh Anandh
Date:2013-10-05
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:variation on RMID