C++  Easy Deque + Ordered Map  [Add O(logM) Avg O(K) Space O(M)]
Idea\n##### addElement\n- Use a deque to keep track of the last m elements.\n- Use a ordered map to store the m elements in order.\n- Use a varaiable sum to sum
### Idea\n##### addElement\n- Use a deque to keep track of the last m elements.\n- Use a ordered map to store the m elements in order.\n- Use a varaiable sum to sum all m elements\n\n#### calculateMKAverage\n- We iterate through the first K and last K elements in ordered map, and subtract them from sum. And calculate the average.\n\n### Time Complexity\nTime:\n- addElement O(logM)\n- calculateMKAverage O(K)\n\nSpace:\n- O(M)\n\n### Code\n```cpp\nclass MKAverage {\npublic:\n    MKAverage(int m, int k): m(m), k(k) {\n        \n    }\n    \n    void addElement(int num) {\n        //O(logN)\n        dq.push_back(num);\n        mp[num]++;\n        sum+=num;\n        if(dq.size()>m) {\n            //if there are more then m elements, remove the first element.\n            //from deque and mp.\n            int front = dq.front();\n            mp[front]--;\n            sum-=front;\n            if(mp[front]==0) mp.erase(front);\n            dq.pop_front();\n        }\n    }\n    \n    int calculateMKAverage() {\n        //O(K)\n        if(dq.size()<m) return -1;\n        long long int temp_sum = sum;\n        \n        //normal order: remove smallest k number from sum\n        int temp_k = k;\n        for(auto it = mp.begin(); it!=mp.end(); it++){\n            if(temp_k >= it->second){\n                temp_sum -= it->first*it->second;\n                temp_k-=it->second;\n            }\n            else{\n                temp_sum -= it->first*temp_k;\n                break;\n            }\n        }\n        \n        //reverse order: remove largest k number from sum\n        temp_k = k;\n        for(auto it = mp.rbegin(); it!=mp.rend(); it++){\n            if(temp_k >= it->second){\n                temp_sum -= it->first*it->second;\n                temp_k-=it->second;\n            }\n            else{\n                temp_sum -= it->first*temp_k;\n                break;\n            }\n        }\n        \n        return temp_sum/(m-2*k);\n    }\nprivate:\n    const int m = 0;\n    const int k = 0;\n    deque<int> dq; //used for keeping only m elements\n    map<int, int> mp; //act as an sorted array\n    long long int sum = 0; //the sum of current m numbers.\n};\n```
[]