EC_ESTA  Statistics Applied
In this problem we will be looking for medians of data set. Median is the central element in ordered data group. For example: for the set {2,6,3,3,2} the median would be 3. In general, if we have n elements {a1, a2, a3 ... an}, we define the median as element a_{(n+1)/2} if n is odd and (a_{n/2}+a_{n/2+1})/2 otherwise.
You will be given N numbers and you must calculate N medians. ith median is taken on the subset [a_{1}, a_{2}, a_{3}, .., a_{i}] for 1 <= i <= N.
Input
The first line contains the number of test cases. Each case consists of an integer N (1 <= N <= 100000). N integers a_{i} (0 <= a_{i} <2^{31}) follow, elements in data set.
Output
For each case, print N lines with the medians. If the result is nonintegral, print the exact value using decimal point (see example).
Example
Input: 2 4 3 5 7 3 2 3 4
Output: 3 4 5 4 3 3.5
hide comments
Eddy Cael:
20170511 15:53:53
there are two solutions: multiset and also priority_queue. :D 

dwij28:
20161001 23:14:49
TLE for heap ? Seriously ? 

ravi:
20160625 14:44:40
stl prority_queue gives tle ,take care of case when we have to consider middle two elements it doesnot fit in int. 

yash agarwal:
20150603 16:22:54
my id is :14384729


Kunal:
20150418 21:26:55
Shouldn't the fourth output be 6 ?


newbie:
20150315 21:05:58
since median is taken in sorted list.... 

newbie:
20150315 21:04:44
i think second output should be 3 as (3+3)/2=3 & not 4


JordanBelfort:
20140626 23:36:40
nice question :) 

Agus Sentosa Hermawan:
20131219 15:01:05
any tricky case? ._. 
Added by:  Eddy Cael 
Date:  20131026 
Time limit:  0.112s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CPP C++ 4.3.2 JAVA 
Resource:  COMPETENCIA CCBOL2013 