import heapq
def runningMedian(a):
    # Write your code here
    isEven = True
    left, right, output = [], [], []
    heapq.heapify(left)
    heapq.heapify(right)
    
    for n in a:
        if right and n > right[0]:
            if isEven:
                res = heapq.heappushpop(right, n)
                heapq.heappush(left, -1*res)
            else:
                heapq.heappush(right, n)
        else:
            if isEven:
                heapq.heappush(left, -1*n)
            else:
                res = -1*heapq.heappushpop(left, -1*n)
                heapq.heappush(right, res)
        isEven = not isEven
        median = (right[0]-left[0])/2 if isEven else -1*left[0]
        output.append(median)
    return output