class Solution {
public:
    /**
     * 求解合法的(i,j)对的数量
     * @param n int整型 n个人
     * @param m int整型 m个窗口
     * @param a int整型vector 长度为n的vector,顺序表示1-n号客人的办理业务所需时间
     * @return long长整型
     */
    int ans[100010];
    int bbb[100010];
    long long res = 0;
    void _merge(int l,int mid,int r){
        int p1 = l,p2 = mid+1;
        for(int i = l;i <= r;i++) {
            if (p1 <= mid && (p2 > r || ans[p1] <= ans[p2]))
                bbb[i] = ans[p1++];
            else{
                res += mid-p1+1;
                bbb[i] = ans[p2++];
            }
        }
        for(int i = l;i <= r;i++) ans[i] = bbb[i];
    }
    void erfen(int l,int r){
        int mid = (l+r)>>1;
        if(l < mid) erfen(l,mid);
        if(mid+1 < r) erfen(mid+1,r);
        _merge(l,mid,r);
    }
    struct Node{
        int sta; // 起始时间
        int i,j; // 该点位置  需要时间
        Node(int s,int ii,int jj){
            sta = s;
            i = ii;
            j = jj;
        }
        friend bool operator < (const Node &a,const Node &b){
            if(a.sta+a.j < b.sta+b.j)
                return false;
            return true;
        }
    };
    priority_queue<Node> q;
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        // write code here
        int t = 0; // 当前消耗时间
        int i = 0;
        while(true){
            while(q.size() != m){
            	if(i == n) break;
                q.push(Node(t,i,a[i]));
                i++;
            }
            if(i == n) break;
            Node node = q.top();
            q.pop();
            t = node.sta+node.j;
            ans[node.i+1] = t;
        }
        while(!q.empty()){
        	Node kkk = q.top();
        	ans[kkk.i+1] = kkk.sta+kkk.j;
        	q.pop();
		}
        erfen(1,n);
        return res;
    }
};