Running Median

Difficulty: 1800 3500 ms 128 MB

heap

After each value arrives, print the lower median of everything seen so far.

Input: the first line has N; the second line has the N values in arrival order.

Output: N lines: the lower median after each arrival.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

5
1 9 2 8 3

1
1
2
2
3

2
5 3

5
3

Read the Editorial