Description

Given a non-negative integer sequence $A$ of length $N$, find the median for each odd prefix.

Input Format

The first line contains a positive integer $N$. The second line contains $N$ non-negative integers $A_{1\dots N}$.

Output Format

There are $\lfloor \frac{N + 1}2\rfloor$ lines. The $i$-th line is the median of $A_{1\dots 2i - 1}$.

7
1 3 5 7 9 11 6

1
3
5
6

7
3 1 5 9 8 7 6

3
3
5
6

Hint

For 20% of the testdata, $N \le 100$. For 40% of the testdata, $N \le 3000$. For 100% of the testdata, $1 \le N \le 100000$, $0 \le A_i \le 10^9$.

Translated by ChatGPT 5