import heapq

def online_median(stream):

    min_heap = []
    max_heap = []
    results = []

    for i in stream:
        # Mainly we want to keep the min and max heap balanced
        # We want to make sure the max heap is always negative numbers so we have reverse of min heap
        # Below - we push the i into min heap
        # Then we pop the smallest item out of the min heap
        # Then we pop the smallest item from the min heap on to the max heap
        # import pdb; pdb.set_trace();
        heapq.heappush(max_heap, -heapq.heappushpop(min_heap,i))
        # The length of max heap should always be equal or greater than min heap
        # In case of streamed count to be off, min heap will give the median
        # In case of even count, min and max together will give the median
        # Below - we ppop the element out of mac heap and push it min heap when the len of max_heap is greater than min_heap
        if len(max_heap) > len(min_heap):
            heapq.heappush(min_heap, -heapq.heappop(max_heap))

        #print(i)
        # append the results of the emdian stream
        results.append((min_heap[0] - max_heap[0])//2 if len(max_heap) == len(min_heap) else min_heap[0])

    return results

# test1
# test1 = [7,8,1,23,4]
# print(online_median(test1))

# test2
# test2 = [1,2,3,4,5]
# print(online_median(test2))