EC_ESTA - Statistics Applied

no tags 

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 (an/2+an/2+1)/2 otherwise.

You will be given N numbers and you must calculate N medians. i-th median is taken on the subset [a1, a2, a3, .., ai] 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 ai (0 <= ai <231) follow, elements in data set.

Output

For each case, print N lines with the medians. If the result is non-integral, 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: 2017-05-11 15:53:53

there are two solutions: multiset and also priority_queue. :D

dwij28: 2016-10-01 23:14:49

TLE for heap ? Seriously ?

ravi: 2016-06-25 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: 2015-06-03 16:22:54

my id is :14384729
can you tell me the test cases where my solution fails....

Kunal: 2015-04-18 21:26:55

Shouldn't the fourth output be 6 ?
As we will take 5 and 7 for taking out the median !

newbie: 2015-03-15 21:05:58

since median is taken in sorted list....

newbie: 2015-03-15 21:04:44

i think second output should be 3 as (3+3)/2=3 & not 4
||ly, third output as 3 not 5
????

JordanBelfort: 2014-06-26 23:36:40

nice question :)

Agus Sentosa Hermawan: 2013-12-19 15:01:05

any tricky case? ._.


Added by:Eddy Cael
Date:2013-10-26
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