Java TreeSet | Easy to Understand
\nclass MKAverage {\n    TreeSet<Long> small, medium, large;\n    Queue<Long> queue;\n    long sum = 0;\n    int m, k, total;\n    long ind = 0;\n    public MKA
```\nclass MKAverage {\n    TreeSet<Long> small, medium, large;\n    Queue<Long> queue;\n    long sum = 0;\n    int m, k, total;\n    long ind = 0;\n    public MKAverage(int m, int k) {\n        queue = new ArrayDeque();\n        small = new TreeSet();\n        large = new TreeSet();\n        medium = new TreeSet();\n        this.m = m;\n        this.k = k;\n        total = m - 2*k;\n    }\n    \n    // each operation at O(logn)\n    public void addElement(int num) {\n        ind ++;\n        long n = num*1000000L+ind;\n        if(queue.size() < m){\n            queue.add(n);\n            \n            //one time operation - O(nlogn)\n            if(queue.size() == m){\n                List<Long> al = new ArrayList(queue);\n                Collections.sort(al);\n                for(int i=0;i<k;i++){\n                    small.add(al.get(i));\n                }\n                for(int i=k;i<al.size()-k;i++){\n                    sum += al.get(i);\n                    medium.add(al.get(i));\n                }\n                for(int i=al.size()-k;i<al.size();i++){\n                    large.add(al.get(i));\n                }\n            }\n        }else{\n            long val = queue.poll();\n            queue.add(n);\n            \n            long mFirst = medium.first();\n            long mLast = medium.last();\n            if(medium.contains(val)){\n                medium.remove(val);\n                sum -= val;\n            }else if(small.contains(val)){\n                small.remove(val);\n            }else{\n                large.remove(val);\n            }\n            \n            if(n < mFirst){\n                small.add(n);\n            }else if(n > mFirst && n < mLast){\n                medium.add(n);\n                sum += n;\n            }else{\n                large.add(n);\n            }\n            \n            if(large.size() == k+1){\n                long largeFirst = large.first();\n                large.remove(largeFirst);\n                medium.add(largeFirst);\n                sum += largeFirst;\n            }\n            if(small.size() == k+1){\n                long smallLast = small.last();\n                small.remove(smallLast);\n                medium.add(smallLast);\n                sum += smallLast;\n            }\n            if(small.size() == k-1){\n                long mediumFirst = medium.first();\n                small.add(mediumFirst);\n                medium.remove(mediumFirst);\n                sum -= mediumFirst;\n            }\n            if(large.size() == k-1){\n                long mediumLast = medium.last();\n                medium.remove(mediumLast);\n                large.add(mediumLast);\n                sum -= mediumLast;\n            }\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if(queue.size() < m){\n            return -1;\n        }\n        return (int)(sum/(1000000L*total)); \n    }\n}\n```
[]