Core Idea
Maintain the lower half and upper half of the numbers seen so far. The lower median is the largest value in the lower half.
Algorithm
Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Rebalance so the lower half has either the same size or one extra item.
Common Mistakes
When the count is even, this problem asks for the lower median. That means the answer is still the top of the max-heap.