## 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
 < Previous 1 2 3 Next > snitesh24: 2017-12-12 17:59:17 nlogn accepted after replacing cin with getchar_unlocked() in .92 secs kshubham02: 2017-12-06 13:35:31 O(n logn) giving TLE???? What is expected time complexity? Aditya NK: 2017-12-06 09:41:03 Please Note that number of integer in the input is greater than 10^5 but less than 10^6. Cost me a lot of WA and time. saltyfish233: 2017-11-09 23:55:02 Between two test cases (and after the last test case) there is a \n :) geek_lady: 2017-10-28 15:52:09 I am getting TL .can anyone please tell me time complexity of this problem that will be passed? akt_1998: 2017-06-05 21:04:24 Accepted in 0.95 secs ;) sas1905: 2017-06-05 19:40:23 BIT+compression tubamariam: 2017-02-09 05:30:14 why I should sort the list Anand: 2017-01-19 11:33:03 Getting NZEC using Java. Can anyone please specify the input format ? Is there a separate empty line after each test case (after a 0) as it is in http://www.spoj.com/problems/RMID/ ? Any other idea why NZEC ? I am using two heaps to solve EDIT : Use spoj toolkit to see the IO format :) Last edit: 2017-01-19 12:29:59 ANSH KHANNA: 2016-06-25 15:51:08 TL is strict

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