2424. Longest Uploaded Prefix

You are given a stream of n videos, each represented by a distinct number from 1 to n that you need to “upload” to a server. You need to implement a data structure that calculates the length of the longest uploaded prefix at various points in the upload process.

We consider i to be an uploaded prefix if all videos in the range 1 to i (inclusive) have been uploaded to the server. The longest uploaded prefix is the maximum value of i that satisfies this definition.

Implement the LUPrefix class:

• LUPrefix(int n) Initializes the object for a stream of n videos.
• void upload(int video) Uploads video to the server.
• int longest() Returns the length of the longest uploaded prefix defined above.

class LUPrefix {
    int now, ma;
    priority_queue<int, vector<int>, greater<int>> q;
public:
    LUPrefix(int n): now(0), ma(n) {}

    void upload(int video) {
        q.push(video);
        while(q.size() and q.top() == now + 1) {
            now += 1;
            q.pop();
        }
    }

    int longest() {
        return now;
    }
};

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix* obj = new LUPrefix(n);
 * obj->upload(video);
 * int param_2 = obj->longest();
 */