Python3 SortedList
Create a SortedList srr and an array arr.\narr contains all elements in the order they are inserted.\nsrr contains last m elements of arr in sorted order.\nmids
Create a SortedList srr and an array arr.\narr contains all elements in the order they are inserted.\nsrr contains last m elements of arr in sorted order.\nmidsum is the sum of elements of srr excluding 1st k and last k elements.\nWhile taking average size would be n = m - 2 * k\nwhenever a new element has to be inserted, remove (arr.length-m)th element from srr,\ndo this operation while keeping track of midsum so that complexity for addElement() is log(n).\ninserpos() used to determine at what position will a new elemet get inserted when added to srr.\n```\nfrom sortedcontainers import SortedList\nclass MKAverage:\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.arr = []\n        self.srr = SortedList([])\n        self.midsum = 0\n        self.n = self.m - 2*self.k\n    def insertpos(self, x: int) -> int:\n        l = 0\n        r = self.m-1\n        if x<=self.srr[0]:\n            return 0\n        if x>=self.srr[-1]:\n            return self.m\n        while l<=r:\n            m = (l+r)//2\n            if self.srr[m]<x and (m+1==len(self.srr) or self.srr[m+1]>=x):\n                return m+1\n            elif self.srr[m]<x:\n                l = m + 1\n            else:\n                r = m - 1\n        return -1\n    def addElement(self, x: int) -> None:\n        self.arr.append(x)\n        if len(self.arr)==self.m:\n            arr = sorted(self.arr)\n            for i in range(self.k):\n                self.srr.add(arr[i])\n            for i in range(self.k, self.m-self.k):\n                self.srr.add(arr[i])\n                self.midsum += arr[i]\n            for i in range(self.m-self.k, self.m):\n                self.srr.add(arr[i])\n        if len(self.arr)<=self.m:\n            return\n        rem = self.arr[-self.m-1]\n        if rem<=self.srr[self.k-1]:\n            self.srr.remove(rem)\n            ip = self.insertpos(x)\n            if ip>=self.k and ip<=self.m-self.k-1:\n                self.midsum += x - self.srr[self.k-1]\n            elif ip>self.m-self.k-1:\n                self.midsum += self.srr[self.m-self.k-1] - self.srr[self.k-1]\n            self.srr.add(x)\n        elif rem<=self.srr[self.m-self.k-1]:\n            self.srr.remove(rem)\n            ip = self.insertpos(x)\n            self.midsum -= rem\n            if ip<self.k:\n                self.midsum += self.srr[self.k-1]\n            elif ip>=self.k and ip<=self.m-self.k-1:\n                self.midsum += x\n            else:\n                self.midsum += self.srr[self.m-self.k-1]\n            self.srr.add(x)\n        else:\n            self.srr.remove(rem)\n            ip = self.insertpos(x)\n            if ip<self.k:\n                self.midsum += self.srr[self.k-1] - self.srr[self.m-self.k-1]\n            elif ip>=self.k and ip<=self.m-self.k-1:\n                self.midsum += x - self.srr[self.m-self.k-1]\n            self.srr.add(x)\n    def calculateMKAverage(self) -> int:\n        if len(self.arr)<self.m:\n            return -1\n        else:\n            return self.midsum//self.n\n```
[]