2113. Elements in Array After Removing and Replacing Elements

You are given a 0-indexed integer array nums. Initially on minute 0, the array is unchanged. Every minute, the leftmost element in nums is removed until no elements remain. Then, every minute, one element is appended to the end of nums, in the order they were removed in, until the original array is restored. This process repeats indefinitely.

• For example, the array [0,1,2] would change as follows: [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → …

You are also given a 2D integer array queries of size n where queries[j] = [timej, indexj]. The answer to the jth query is:

• nums[indexj] if indexj < nums.length at minute timej
• -1 if indexj >= nums.length at minute timej

Return an integer array ans of size n where ans[j] is the answer to the jth query.

class Solution {
public:
    vector<int> elementInNums(vector<int>& A, vector<vector<int>>& queries) {
        vector<array<int,3>> Q;
        bool pop = true;
        int l = 0, r = A.size(), n = A.size(), now = 0;
        for(int i = 0; i < queries.size(); i++) {
            int t = queries[i][0], idx = queries[i][1];
            Q.push_back({t % (n * 2),idx,i});
        }
        
        vector<int> res(queries.size());
        sort(rbegin(Q), rend(Q));
        
        while(!Q.empty()) {
            auto [t, p, idx] = Q.back();
            if(now != t) {
                if(pop) {
                    if(++l == n) {
                        pop = !pop;
                        l = r = 0;
                    }
                } else {
                    if(++r == n) {
                        pop = !pop;
                    }
                }
                now++;
            } else {
                Q.pop_back();
                int window = r - l - 1;
                if(p > window) res[idx] = -1;
                else {
                    res[idx] = A[p + l];
                }
            }
        }
        return res;
    }
};