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 nondecreasing 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 nondecreasing 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
chetan101:
20180426 19:35:45
Use printf/scanf instead of cin\cout. 

charraster:
20180415 13:54:16
Just solved. You have to use fast buffered IO. I am reading 512bytes at a time, and writing in batches of 32 integers.


coolyansh:
20180322 08:27:14
The required time complexity is O(n log n). Even if the solution is of the required complexity TLE or WA can occur because of the following reasons:


avjot_singh99:
20180301 09:53:56
Accepted in 0.20s


anhtuan_77:
20180130 14:47:55
TLE :(


v_pp_27:
20171215 07:50:21
after lots WAs, runtime errors,tle ...finally solved it.... : ). Last edit: 20171215 07:54:24 

snitesh24:
20171212 17:59:17
nlogn accepted after replacing cin with getchar_unlocked() in .92 secs 

kshubham02:
20171206 13:35:31
O(n logn) giving TLE???? What is expected time complexity? 

Aditya NK:
20171206 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:
20171109 23:55:02
Between two test cases (and after the last test case) there is a \n :) 
Added by:  Akhilesh Anandh 
Date:  20131005 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  variation on RMID 