P1168 Median

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

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

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

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