# Using Insertion sort
# Time Complexity : O(n^2)
# Auxiliary Space: O(1)

def online_median(stream):

    results = []
    for i in range(len(stream)):
        # stream[0..j-1] is already sorted
        # insert stream[j] at the correct position in order to keep stream[0...j] sorted
        j = i
        while j > 0 and stream[j] > stream[j-1]:
            stream[j], stream[j-1] = stream[j-1], stream[j]
            j = j-1

        if i % 2 == 0:
            results.append(stream[i//2])
        else:
            results.append((stream[i//2] + stream[i//2 + 1]) // 2)
    return results