XMEDIAN - Median

no tags 

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: 2017-06-25 18:58:48

wtf Getting continuously TLE in CPP14 and AC in CPP 4.3.2

muaz: 2015-07-29 23:34:56

accepted in 0.22 sec .. use printf

xaverius: 2013-01-01 09:39:41

need tricky test case

Parag gupta: 2011-08-15 09:25:38

with "cout" it gives TLE (above 2 secs).
with "printf" got accepted in 1.2 secs !!

[Rampage] Blue.Mary: 2010-04-13 13:56:20

See the problem WEIRDFN.


Added by:Spooky
Date:2010-04-13
Time limit:0.189s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET