You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:


	If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
	Remove the smallest k elements and the largest k elements from the container.
	Calculate the average value for the rest of the elements rounded down to the nearest integer.


Implement the MKAverage class:


	MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.
	void addElement(int num) Inserts a new element num into the stream.
	int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.


&nbsp;
Example 1:

Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]

Explanation
MKAverage obj = new MKAverage(3, 1); 
obj.addElement(3);        // current elements are [3]
obj.addElement(1);        // current elements are [3,1]
obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist.
obj.addElement(10);       // current elements are [3,1,10]
obj.calculateMKAverage(); // The last 3 elements are [3,1,10].
                          // After removing smallest and largest 1 element the container will be [3].
                          // The average of [3] equals 3/1 = 3, return 3
obj.addElement(5);        // current elements are [3,1,10,5]
obj.addElement(5);        // current elements are [3,1,10,5,5]
obj.addElement(5);        // current elements are [3,1,10,5,5,5]
obj.calculateMKAverage(); // The last 3 elements are [5,5,5].
                          // After removing smallest and largest 1 element the container will be [5].
                          // The average of [5] equals 5/1 = 5, return 5


&nbsp;
Constraints:


	3 &lt;= m &lt;= 105
	1 &lt;= k*2 &lt; m
	1 &lt;= num &lt;= 105
	At most 105 calls will be made to addElement and calculateMKAverage.


from sortedcontainers import SortedList

class MKAverage:

    MAX_NUM = 10 ** 5
    def __init__(self, m: int, k: int):
        
        self.m = m
        self.k = k
        
        # sorted list
        self.sl = SortedList([0] * m)
		# sum of k smallest elements
        self.sum_k = 0
		# sum of m - k smallest elements
        self.sum_m_k = 0
        
        # queue for the last M elements if the stream
        self.q = deque([0] * m)
        
    def addElement(self, num: int) -> None:
        # Time: O(logm)
		
        m, k, q, sl = self.m, self.k, self.q, self.sl            
            
        # update q
        q.append(num)
        old = q.popleft()
        
        # remove the old num
        r = sl.bisect_right(old)
		# maintain sum_k
        if r <= k:
            self.sum_k -= old
            self.sum_k += sl[k]
		# maintain sum_m_k
        if r <= m - k:
            self.sum_m_k -= old
            self.sum_m_k += sl[m-k]
        # remove the old num
        sl.remove(old)
        
        # add the new num
        r = sl.bisect_right(num)
        if r < k:
            self.sum_k -= sl[k-1]
            self.sum_k += num
        if r < m - k:
            self.sum_m_k -= sl[m - k - 1]
            self.sum_m_k += num
        
        sl.add(num)
            
        return

    def calculateMKAverage(self) -> int:
		# Time: O(1)
        if self.sl[0] == 0:
            return -1
        return (self.sum_m_k - self.sum_k) // (self.m - self.k * 2)
class MKAverage {
    class Node implements Comparable<Node> {
        int val;
        int time;
        
        Node(int val, int time) {
            this.val = val;
            this.time = time;
        }
        
        @Override
        public int compareTo(Node other) {
            return (this.val != other.val ? this.val - other.val 
                                          : this.time - other.time);
        }
    }
    
    private TreeSet<Node> set = new TreeSet<>();          // natural order
    private Deque<Node> queue = new LinkedList<>();
    private Node kLeft;
    private Node kRight;
    
    private int m, k;
    
    private int time = 0;
    private int sum = 0;

    public MKAverage(int m, int k) {
        this.m = m;
        this.k = k;
    }
    
    public void addElement(int num) {
        Node node = new Node(num, time++);

        addNode(node);
        removeNode();
        
        if (time == m) init();
    }
    
    private void init() {
        int i = 0;
        for (Node node : set) {
            if (i < k-1);
            else if (i == k-1) kLeft = node;
            else if (i < m-k) sum += node.val;
            else if (i == m-k) {
                kRight = node;
                return;
            }
            
            i++;
        }
        return;
    }
    
    private void addNode(Node node) {
        queue.offerLast(node);
        set.add(node);
        
        if (queue.size() <= m) return;
        
        if (node.compareTo(kLeft) < 0) {
            sum += kLeft.val;
            kLeft = set.lower(kLeft);
        } else if (node.compareTo(kRight) > 0) {
            sum += kRight.val;
            kRight = set.higher(kRight);
        } else {
            sum += node.val;
        } 
    }
    
    private void removeNode() {
        if (queue.size() <= m) return;
        
        Node node = queue.pollFirst();
        
        if (node.compareTo(kLeft) <= 0) {
            kLeft = set.higher(kLeft);
            sum -= kLeft.val;
        } else if (node.compareTo(kRight) >= 0) {
            kRight = set.lower(kRight);
            sum -= kRight.val;
        } else {
            sum -= node.val;
        }
        
        set.remove(node);
    }
    
    public int calculateMKAverage() {
        return (queue.size() < m ? -1 : sum / (m - 2 * k));
    }
}
/* 
    Time: addElement: O(logm) | calculateMKAverage: O(1)
    Space: O(m)
    Tag: TreeMap, Sorting, Queue
    Difficulty: H
*/

class MKAverage {
    map<int, int> left, middle, right;
    queue<int> q;
    int sizeofLeft, sizeofMiddle, sizeofRight;
    int k;
    long long mkSum;
    int m;

    void addToSet1(int num) {
        left[num]++;
        sizeofLeft++;
    }

    void deleteFromSet1(int num) {
        left[num]--;
        if (left[num] == 0) left.erase(num);
        sizeofLeft--;
    }

    void addToSet2(int num) {
        middle[num]++;
        sizeofMiddle++;
        mkSum += num;
    }

    void deleteFromSet2(int num) {
        middle[num]--;
        if (middle[num] == 0) middle.erase(num);
        sizeofMiddle--;
        mkSum -= num;
    }

    void addToSet3(int num) {
        right[num]++;
        sizeofRight++;
    }

    void deleteFromSet3(int num) {
        right[num]--;
        if (right[num] == 0) right.erase(num);
        sizeofRight--;
    }

public:
    MKAverage(int m, int k) {
        sizeofLeft = 0, sizeofMiddle = 0, sizeofRight = 0;
        mkSum = 0;
        this->k = k;
        this->m = m;
    }

    void addElement(int num) {
        if (sizeofLeft < k) {
            addToSet1(num);
            q.push(num);
        } else if (sizeofMiddle < (m - (2 * k))) {
            int lastEle = prev(left.end())->first;
            if (num >= lastEle) {
                addToSet2(num);
            } else {
                deleteFromSet1(lastEle);
                addToSet1(num);
                addToSet2(lastEle);
            }
            q.push(num);
        } else if (sizeofRight < k) {
            int last1 = prev(left.end())->first;
            int last2 = prev(middle.end())->first;
            if (num >= last1 && num >= last2) {
                addToSet3(num);
            } else if (num >= last1 && num < last2) {
                deleteFromSet2(last2);
                addToSet2(num);
                addToSet3(last2);
            } else {
                deleteFromSet2(last2);
                addToSet3(last2);
                deleteFromSet1(last1);
                addToSet2(last1);
                addToSet1(num);
            }
            q.push(num);
        } else {
            int toErase = q.front();
            q.pop();
            int first3 = right.begin()->first;
            int first2 = middle.begin()->first;
            int first1 = left.begin()->first;

            if (toErase >= first3) {
                deleteFromSet3(toErase);
            } else if (toErase >= first2) {
                deleteFromSet3(first3);
                deleteFromSet2(toErase);
                addToSet2(first3);
            } else {
                deleteFromSet3(first3);
                deleteFromSet2(first2);
                deleteFromSet1(toErase);
                addToSet1(first2);
                addToSet2(first3);
            }
            addElement(num);
        }
    }

    int calculateMKAverage() {
        if (q.size() < m) return -1;
        return mkSum / (m - (2 * k));
    }
};
class ArraySegTree{
    // Array to perfrom operations on, range query operation, PointUpdate operation
    constructor(A,op=(a,b)=>a+b,upOp=(a,b)=>a+b,opSentinel=0){
        this.n=A.length,this.t=[...Array(4*this.n+1)],this.op=op,this.upOp=upOp,this.opSentinel=opSentinel
        //root's idx =1
        this.build(A,1,0,this.n-1)
    }
    left=x=>this.t[2*x];right=x=>this.t[2*x+1]
    build(A,idx,left,right){
        if(left==right)
            return this.t[idx]=A[left]
        let mid=(left+right)>>1
        this.build(A,2*idx,left,mid) //go left
        this.build(A,2*idx+1,mid+1,right) //go right
        this.t[idx]=this.op(this.left(idx),this.right(idx)) //merge
    }
    //just specify l,r on actual queries
    //Here queries use the actul indices of the starting array A, so rangeQuery(0,n-1) returns the whole array
    rangeQuery=(l,r,tl=0,tr=this.n-1,idx=1)=>{
        if(l>r)
            return this.opSentinel
        if(l===tl&&r===tr)
            return this.t[idx]
        let mid=(tl+tr)>>1
        return this.op(
                this.rangeQuery(l,Math.min(r,mid),tl,mid,idx*2),
                this.rangeQuery(Math.max(l,mid+1),r,mid+1,tr,idx*2+1)
        )
    }
    //just specify arrIdx,newVal on actual pointUpdates
    pointUpdate=(arrIdx,newVal,tl=0,tr=this.n-1,idx=1)=>{
        if(tl==tr)
            return this.t[idx]=this.upOp(this.t[idx],newVal)
        let mid=(tl+tr)>>1
        if(arrIdx<=mid)
            this.pointUpdate(arrIdx,newVal,tl,mid,2*idx)
        else
            this.pointUpdate(arrIdx,newVal,mid+1,tr,2*idx+1)
        this.t[idx]=this.op(this.left(idx),this.right(idx))
    }
    seachPrefixIndex=(x,start=0,end=this.n-1)=>{
        let s=this.rangeQuery(start,end)
        if(s<x)
            return -1
        if(start===end)
            return start
        let mid=start+end>>1,left=this.rangeQuery(start,mid)
        if( left>=x)
            return this.seachPrefixIndex(x,start,mid)
        else
            return this.seachPrefixIndex(x-left,mid+1,end)
    }
}

var MKAverage = function(m, k) {
    this.A=[],this.m=m,this.k=k,this.div=m-2*k
    this.S1=new ArraySegTree([...Array(1e5+2)].map(d=>0))//indices
    this.S2=new ArraySegTree([...Array(1e5+2)].map(d=>0))//sums
};

/**
 * @param {number} num
 * @return {void}
 */
MKAverage.prototype.addElement = function(num) {
    this.A.push(num)
    this.S1.pointUpdate(num,1)
    this.S2.pointUpdate(num,num)
    if(this.A.length>this.m){
        let z=this.A.shift()
        this.S1.pointUpdate(z,-1)
        this.S2.pointUpdate(z,-z)
    }
};

/**
 * @return {number}
 */
MKAverage.prototype.calculateMKAverage = function() {
    if(this.A.length<this.m)
        return -1

    let S=this.S1.seachPrefixIndex(this.k+1),
        count1=this.S1.rangeQuery(0,S),
        take=(count1-this.k)*S

    let E=this.S1.seachPrefixIndex(this.m-this.k),
        count2=this.S1.rangeQuery(0,E),
        remove=(count2-this.m+this.k)*E

    let midSum=this.S2.rangeQuery(S+1,E)
    return (take+midSum-remove)/this.div>>0
};
Finding MK Average