Multiset Approach Easy to Understand
\n#define ll long long int\nclass MKAverage {\n    ll m,k,tot,midsum;\n    queue<ll> dq;\n    multiset<ll> low,mid,high;\npublic:\n    MKAverage(int M, int K) {
```\n#define ll long long int\nclass MKAverage {\n    ll m,k,tot,midsum;\n    queue<ll> dq;\n    multiset<ll> low,mid,high;\npublic:\n    MKAverage(int M, int K) {\n        low.clear(); // store k smallest numbers in latest stream of m numbers\n        high.clear();// stores k largest numbers in latest stream of m numbers\n        mid.clear(); // stores the remaining numbers of the curr stream of numbers\n        midsum=0; // sum of elements in middle midset\n        m=M;\n        tot=0; // intialized tot number of elements\n        k=K;\n    }\n    \n    void addElement(int num) {\n\t\t// push the current element into queue\n        dq.push(num);\n\t\t// if number of elements < k then insert into smaller set only\n        if(low.size()<k)\n            low.insert(num);\n        \n        else{\n\t\t\t// initiallly we only fill low and high multisets\n            if(high.size()<k){\n                auto it=low.end();\n                --it;\n                // if given element is greater than current max of all k smallest\n                if(*it<=num)\n                    high.insert(num); // insert into high multiset\n                else{\n\t\t\t\t\t// else insert new element into low and max from low into high multiset\n                    int val=*it;\n                    low.erase(it);\n                    high.insert(val);\n                    low.insert(num);\n                }\n            }\n            // if tot >= 2*k\n\t\t\t// now we need to insert elements into middle set depending upon the following conditions\n            else{\n                auto it=low.end();\n                --it;\n                auto it2=high.begin();\n\t\t\t\t// if current number is one of the smallest then insert into low\n\t\t\t\t// insert the max of low into middle set\n                if(num<*it){\n                    ll val=*it;\n                    low.erase(it);\n                    mid.insert(val);\n                    midsum+=val;\n                    low.insert(num);\n                }\n                \n\t\t\t\t// if curr number is one of the k largest put into high\n\t\t\t\t// put the smallest from high into middle set\n                else if(num>*it2){\n                    ll val=*it2;\n                    high.erase(it2);\n                    mid.insert(val);\n                    midsum+=val;\n                    high.insert(num);\n                }\n                \n\t\t\t\t// if curr number itself lies in middle set inherently\n                else{\n                    mid.insert(num);\n                    midsum+=num;\n                }\n\t\t\t\t\n\t\t\t\t// if we have more than m elements we need to remove the oldest element from front of queue\n\t\t\t\t// we search for that element in three sets and do the needful maintainigng the size of low and high always equal to k\n                if(dq.size()==m+1){\n                    ll f=dq.front();\n                    dq.pop();\n\t\t\t\t\t// if element in middle then delete from middle set and just be done with it\n                    if(mid.find(f)!=mid.end()){\n                        mid.erase(mid.find(f));\n                        midsum-=f;\n                    }\n\t\t\t\t\t// deletion from low decreases its size so need to insert one of the smaller element from middle set\n                    else if(low.find(f)!=low.end()){\n                        low.erase(low.find(f));\n                        auto it=mid.begin();\n                        ll val=*it;\n                        midsum-=val;\n                        mid.erase(it);\n                        low.insert(val);\n                    }\n\t\t\t\t\t// deletion from high reduces its size so we insert the max from middle into high set\n                    else{\n                        high.erase(high.find(f));\n                        auto it=mid.end();\n                        --it;\n                        ll val=*it;\n                        mid.erase(it);\n                        midsum-=val;\n                        high.insert(val);\n                    }\n                } \n            }\n        }\n    }    \n    \n    int calculateMKAverage() {\n        ll ls=low.size(),ms=mid.size(),hs=high.size();\n        tot=ls+ms+hs;\n\t\t// if tot size < m\n        if(tot<m)\n            return -1;\n\t\t// calculating the average\n        ll mss=mid.size();\n        ll ans=(midsum)/mss;\n        return ans;\n    }\n};\n```
['C', 'C++']