from heapq import heappush, heappop
class Median:
    def __init__(self):
        self.maxHeap, self.minHeap = [], []
    
    def addNum(self, num):
        heappush(self.maxHeap, -num)
        
        if self.minHeap and self.maxHeap and -self.maxHeap[0] > self.minHeap[0]:
            heappush(self.minHeap, -heappop(self.maxHeap))
        
        if len(self.minHeap) > len(self.maxHeap) + 1:
            heappush(self.maxHeap, -heappop(self.minHeap))
        
        if len(self.maxHeap) > len(self.minHeap) + 1:
            heappush(self.minHeap, -heappop(self.maxHeap))
            
    def findMedian(self):
        if len(self.maxHeap) > len(self.minHeap):
            return float(-self.maxHeap[0])
        
        if len(self.maxHeap) < len(self.minHeap):
            return float(self.minHeap[0])
        else:
            return (self.minHeap[0] - self.maxHeap[0]) / 2
        
def runningMedian(a):
    obj = Median()
    result = list()
    for i in a:
        obj.addNum(i)
        result.append(obj.findMedian())
    return result