"""
295
find median from data stream
hard
"""

from heapq import *


class MedianFinder:

    # max heap and min heap

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.hi = []
        self.lo = []

    def addNum(self, num: int) -> None:
        heappush(self.lo, -heappushpop(self.hi, num))
        while len(self.lo) > len(self.hi):
            heappush(self.hi, -heappop(self.lo))


    def findMedian(self) -> float:
        if len(self.hi) > len(self.lo):
            return self.hi[0]
        if len(self.hi) == len(self.lo):
            return (self.hi[0] - self.lo[0]) / 2.0




sol = MedianFinder()
sol.addNum(1)
print(sol.findMedian())
sol.addNum(2)
print(sol.findMedian())
[]