Segment Tree Solution
\nclass MKAverage {\npublic:\n    #define LL long long\n    struct node {\n        int frq;\n        LL sum;\n        \n        node() { frq = 0; sum = 0; }\n  
```\nclass MKAverage {\npublic:\n    #define LL long long\n    struct node {\n        int frq;\n        LL sum;\n        \n        node() { frq = 0; sum = 0; }\n        node(int _frq, LL _sum): frq(_frq), sum(_sum) {}\n    };\n    \n    node Tree[100005 * 4];\n    const int limit = 100000;\n\n    \n    node merge_segments(const node &lf, const node &rt) {\n        return node(lf.frq + rt.frq, lf.sum + rt.sum);\n    }\n    \n    void update(int node, int b, int e, int pos, int add) {\n        if (b == e) {\n            Tree[node].frq += add;\n            Tree[node].sum += (add * pos);\n            return ;\n        }\n        int mid = (b + e) >> 1;\n        int lf = node << 1;\n        int rt = lf | 1;\n        \n        if (pos <= mid) update(lf, b, mid, pos, add);\n        else update(rt, mid + 1, e, pos, add);\n        \n        Tree[node] = merge_segments(Tree[lf], Tree[rt]);\n    }\n    \n    \n    LL get_left_kth_sum(int node, int b, int e, int kth) {\n        if (kth <= 0) return 0;\n        if (kth >= Tree[node].frq) return Tree[node].sum;\n        if (b == e) {\n            return kth * 1LL * b;\n        }\n        \n        int mid = (b + e) >> 1;\n        int lf = node << 1;\n        int rt = lf | 1;\n        \n        return get_left_kth_sum(lf, b, mid, kth) + get_left_kth_sum(rt, mid + 1, e, kth - Tree[lf].frq);\n    }\n    \n    LL get_right_kth_sum(int node, int b, int e, int kth) {\n        if (kth <= 0) return 0;\n        if (kth >= Tree[node].frq) return Tree[node].sum;\n        if (b == e) {\n            return kth * 1LL * b;\n        }\n        \n        int mid = (b + e) >> 1;\n        int lf = node << 1;\n        int rt = lf | 1;\n        \n        return get_right_kth_sum(lf, b, mid, kth - Tree[rt].frq) + get_right_kth_sum(rt, mid + 1, e, kth);\n    }\n    \n    int M, K;\n    queue <int> window;\n\n    MKAverage(int m, int k) {\n        M = m;\n        K = k;\n    }\n    \n    void addElement(int num) {\n        window.push(num);\n        update(1, 0, limit, num, +1);\n        \n        if (window.size() > M) {\n            update(1, 0, limit, window.front(), -1);\n            window.pop();\n        }\n        \n    }\n    \n    int calculateMKAverage() {\n        if (window.size() < M) return -1;\n        LL total = Tree[1].sum;\n        LL left_k_sum = get_left_kth_sum(1, 0, limit, K);\n        LL right_k_sum = get_right_kth_sum(1, 0, limit, K);\n        \n        \n        return (total - left_k_sum - right_k_sum) / (M - 2 * K);\n    }\n};\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage* obj = new MKAverage(m, k);\n * obj->addElement(num);\n * int param_2 = obj->calculateMKAverage();\n */\n```
[]