Find Median from Data Stream

Numbers arrive one at a time. Support two operations:

• add x — add the number x
• median — print the median of all numbers added so far (for an even count, the average of the two middle numbers)

Input:

• line 1: q
• next q lines: one operation each. The first operation is always an add.

Output: one line per median, with exactly one digit after the decimal point (2.0, -1.5).

Constraints: 1 ≤ q ≤ 10⁵, −10⁵ ≤ x ≤ 10⁵.

The design: keep the smaller half in a max-heap and the larger half in a min-heap, with sizes differing by at most one. The median is then the top of one heap or the average of both tops: O(log n) per add, O(1) per median. Sorting after every add is far too slow for the big tests.