[Python] SortedList solution
There is a sortedcontainers package for Python (link), which I think is a good alternative for red-black tree or ordered map for python players.\nUsing SortedLi
There is a `sortedcontainers` package for Python ([link](http://www.grantjenks.com/docs/sortedcontainers/index.html)), which I think is a good alternative for red-black tree or ordered map for python players.\nUsing `SortedList`, it takes `~ O(logn)` time for both remove and insert. (Since `SortedList` is based on list of list, instead of tree structure, the time cost is not exactly `O(logn)`)\n\n```\nfrom sortedcontainers import SortedList\n\nclass MKAverage:\n\n    MAX_NUM = 10 ** 5\n    def __init__(self, m: int, k: int):\n        \n        self.m = m\n        self.k = k\n        \n        # sorted list\n        self.sl = SortedList([0] * m)\n\t\t# sum of k smallest elements\n        self.sum_k = 0\n\t\t# sum of m - k smallest elements\n        self.sum_m_k = 0\n        \n        # queue for the last M elements if the stream\n        self.q = deque([0] * m)\n        \n    def addElement(self, num: int) -> None:\n        # Time: O(logm)\n\t\t\n        m, k, q, sl = self.m, self.k, self.q, self.sl            \n            \n        # update q\n        q.append(num)\n        old = q.popleft()\n        \n        # remove the old num\n        r = sl.bisect_right(old)\n\t\t# maintain sum_k\n        if r <= k:\n            self.sum_k -= old\n            self.sum_k += sl[k]\n\t\t# maintain sum_m_k\n        if r <= m - k:\n            self.sum_m_k -= old\n            self.sum_m_k += sl[m-k]\n        # remove the old num\n        sl.remove(old)\n        \n        # add the new num\n        r = sl.bisect_right(num)\n        if r < k:\n            self.sum_k -= sl[k-1]\n            self.sum_k += num\n        if r < m - k:\n            self.sum_m_k -= sl[m - k - 1]\n            self.sum_m_k += num\n        \n        sl.add(num)\n            \n        return\n\n    def calculateMKAverage(self) -> int:\n\t\t# Time: O(1)\n        if self.sl[0] == 0:\n            return -1\n        return (self.sum_m_k - self.sum_k) // (self.m - self.k * 2)\n```
['Python']