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
JordanBelfort: 2014-06-26 23:36:40

nice question :)

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

any tricky case? ._.

Anshul: 2013-11-16 22:41:21

I am using priorty queue still TLE, any better approach exists?

sunriser: 2013-11-14 19:53:36

My code works fine for a few sample cases..can u tell where it is going wrong??

[Lakshman]: 2013-10-31 17:13:19

Can some one help me. I am using quickselect algorithm but getting TLE is there any better algorithm for this..?

(abdou).. you can use priority queue :D
(Lakshman)-> Got AC.

Last edit: 2013-11-13 08:21:25
Akhilesh Anandh: 2013-10-30 05:40:33

Problem statement not very clear.

wisfaq: 2013-10-27 10:05:51

Please undo unnecessary language restrictions.

Eddy Cael: 2013-10-26 19:52:28

Hi Abhimanyu Singh, the problem is correct and the sample too... Thanks.

AvmnuSng: 2013-10-26 19:52:28

@PS : You have written formulas for incorrect cases of n (total no. of elements).

and your sample input is in sorted order, does it mean that input will be in sorted order ?

Last edit: 2013-10-26 13:01:46

Added by:Eddy Cael
Date:2013-10-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:COMPETENCIA CCBOL2013