Java BIT/Fenwick 60ms
\nclass MKAverage {\n    Deque<Integer> queue;\n    Bit countBit;\n    Bit valueBit;\n    int m;\n    int k;\n    public MKAverage(int m, int k) {\n        queu
```\nclass MKAverage {\n    Deque<Integer> queue;\n    Bit countBit;\n    Bit valueBit;\n    int m;\n    int k;\n    public MKAverage(int m, int k) {\n        queue = new ArrayDeque();\n        countBit = new Bit(100001);\n        valueBit = new Bit(100001);\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void addElement(int num) {\n        queue.addLast(num);\n        countBit.add(num, 1);\n        valueBit.add(num, num);\n        if(queue.size()>m)\n        {\n            var polledNum = queue.pollFirst();\n            countBit.add(polledNum, -1);\n            valueBit.add(polledNum, -polledNum);\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if(queue.size() < m)\n            return -1;\n        \n\t\t// Get first k elements index\n        var left = binarySearch(k);\n\t\t\n\t\t// Get last k elements index\n        var right = binarySearch(m-k);\n        \n        // Ex: [5 5 5] \n        // left and right are equal, so difference is 0. What this means is the answer is at either left or right.\n        // Using the countBit we can calculate the correct sum at index left.\n        // Thats why we also have to do step 1 and step 2. \n        long result = valueBit.sum(right) - valueBit.sum(left); \n        \n        result += (countBit.sum(left) - k)*left; // step 1\n        result -= (countBit.sum(right) - m + k)*right; // step 2\n        \n        return (int)(result/(m-2*k));\n    }\n    \n    public int binarySearch(int val)\n    {\n        int l = 0;\n        int r = 100001;\n        while(l<r)\n        {\n            int mid = l + (r-l)/2;\n            if(countBit.sum(mid) < val)\n                l = mid + 1;\n            else \n                r = mid;\n        }\n        \n        return l;\n    }\n    \n    \n    class Bit\n    {\n\t    // Use long because the sum can exceed Integer.MAX_VALUE\n        long[] bit;\n        public Bit(int size)\n        {\n\t\t\t// 1-indexed\n            bit = new long[size+1];\n        }\n        \n        public void add(int num, int value)\n        {         \n            num += 1;\n            while(num < bit.length)\n            {\n                bit[num] += value;              \n                num += num & (-num);\n            }\n        }\n    \n        public long sum(int num)\n        {\n            long s = 0;\n            num += 1;\n            while(num>0)\n            {\n                s += bit[num];\n                num &= num-1;\n            }\n            \n            return s;\n        }\n    }\n}\n```
[]