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
deependra_18:
20191015 18:08:53
Getting TLE when not using FAST I/O ) 

ab17_best:
20191007 12:38:23
AC in one go!! Comments were useful


wingman__7:
20191004 15:27:24
Take care of putting new line character after each test case it cost me 2 WA :( 

rajat_singhal:
20190906 12:06:47
Insert Extra line after every test case 

kshitij_sodani:
20190529 15:15:01
I am solving this problems using 2 heaps with the most optimal approach still getting TLE. Is this problem even solvable in python. Does SPOJ has time multiplier for slow languages like python like codechef and hackerearth have a time multiplier of 5 for python 

tarungupta:
20190507 09:37:06
AC in one go! priority queue min and max worked. 

mayank_soni055:
20181005 22:25:45
Use fast_io in c++ with cin/cout 

shrikant_7:
20180814 08:09:30
very strict time constraints for java. No submission in java till now. switch to cpp 

uselesscoder:
20180812 11:06:29
AC In one go :) 

be1035016:
20180617 18:13:18
O(nlogn) accepted.used fast i/o with cin/cout.good problem.took lots of thinking 
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 