The one with the password

0

0 votes
Easy-Medium
Problem

Nobody really knows what Chandler's job is. Some say it has something to do with numbers, but what exactly nobody knows.

Joey, being Chandler's room mate and best friend, decides to look into his laptop to see if he can get any real clue. But he finds that all the files are locked with some weird kind of lock - where in he had to input some number for each number appearing on the screen. Joey had heard Chandler talk something about finding the middle number of all the numbers that appeared on the screen.

Now, as Joey was busy doing other things in high school - he doesn't know that he has to find the median of all the numbers as they appear on the screen. But you, being his friend, immediately understand this and decide to help him

Input

The first line of the input contains a number N, which is number of integers appearing on the screen. Next line contains N integers.

Output

For every integer, print the integral value of the median of all the numbers till that position.

Constraints

0<N<=100000

0<X<=1000000000

Sample Input

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Editor Image

?