XMEDIAN  Median
Given an array x of n elements find the medians of its first k elements for each k from 1 to n inclusive. The median of an array is the middle element of that array when it is sorted. If there are an even number of elements in the array, we choose the first of the middle two elements to be the median.
Input
The first line of input contains number n (1 <= n <= 200000)  the amount of elements in the array. The next n lines contain the elements xi (1 <= xi <= 1000000).
Output
Output n integers  the medians of the first k elements of the array for each k from 1 to n inclusive.
Example
Input: 5 1 2 3 4 5 Output: 1 1 2 2 3
hide comments
rajeev_899:
20170625 18:58:48
wtf Getting continuously TLE in CPP14 and AC in CPP 4.3.2 

muaz:
20150729 23:34:56
accepted in 0.22 sec .. use printf 

xaverius:
20130101 09:39:41
need tricky test case 

Parag gupta:
20110815 09:25:38
with "cout" it gives TLE (above 2 secs).


[Rampage] Blue.Mary:
20100413 13:56:20
See the problem WEIRDFN. 
Added by:  Spooky 
Date:  20100413 
Time limit:  0.189s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 