Python [short solution]
Warning: As the wonderful test cases have been updated, now the code gets TLE.\n\nThis one is slightly outlandish as I use the SortedList from sortedcontainers 
**Warning: As the wonderful test cases have been updated, now the code gets TLE.**\n\nThis one is slightly outlandish as I use the `SortedList` from `sortedcontainers` class - it\'s not part of standard library. With that said this container proves useful in several questions, such as "1649. Create Sorted Array through Instructions".\n\nAnyway, `SortedList` insertions are, well, sorted. So at any time you can find the desired average simply by `sum(self.slist[self.k:-self.k]) // (self.m - 2*self.k)`. We use a queue to keep the least recently used entries and remove when necessary. For that purpose the built-in removel tool of `SortedList` is fast.\n\n```python\nimport collections\nimport sortedcontainers\nclass MKAverage:\n    def __init__(self, m, k):\n        self.m = m\n        self.k = k\n        self.que = collections.deque([])\n        self.slist = sortedcontainers.SortedList()\n        \n\n    def addElement(self, num):\n        self.que.append(num)\n        self.slist.add(num)\n        if len(self.que) > self.m:\n            lru = self.que.popleft()\n            self.slist.remove(lru)\n\n            \n    def calculateMKAverage(self):\n        if len(self.que) < self.m:\n            return -1\n        return sum(self.slist[self.k:-self.k]) // (self.m - 2*self.k)\n```
[]