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 (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
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 |