Running Median

Interview

Time limit0.1sMemory limit128 MB

Summary

Given integers one by one, output the running median (lower of the two middles when count is even) after each insertion.

Level: Medium5 of 10
Topics: Heap, Sorting, Implementation
Solved: No attempts yet

Problem

Integers are given one at a time. After each integer is added, output the median of all integers seen so far after sorting them.

If the number of integers seen so far is even, the median is defined as the smaller of the two middle values. Write a program that outputs this value after every input integer.

Input

The first line contains the number of integers N. 1 <= N <= 100,000.

Each of the next N lines contains one integer in order. For every integer x, -10,000 <= x <= 10,000.

Output

Print N lines. On each line, print the median immediately after reading the corresponding integer.

Examples1

Example 1
Input
```
7
1
5
2
10
-99
7
5
```
Expected output
```
1
1
2
2
2
2
5
```