Rolling Median

Problem Statement

You are given a list $x$ of $n$ integers $x = [x_1, x_2, ..., x_n]$.

You wish to determine the median for each prefix of $x$. For example given $[1, 2, 9, 7]$, you want to determine:

• The median of $[1]$, then
• The median of $[1, 2]$, then
• The median of $[1, 2, 9]$, then
• The median of $[1,2,9,7]$

Input Format

Your first line of input will contain a single integer $n$. Your next line will contain $n$ integers space-separated representing $x$.

Output Format

You should output $n$ space-separated integers representing the median of each prefix of $x$.

Constraints

• $1 \leq n \leq 10^5$
• $-10^9 \leq x_i \leq 10^9$

Sample Cases

10
1 2 9 7

1 1.5 2 5.5

Explanation 1

There are 7 integers less than 14, being $-2, 1, 2, 4, 5, 6, 10$. There are 4 integers less than 5, being $-2, 1, 2, 4$. There are 6 integers less than 7, being $-2, 1, 2, 4, 5, 6$.