First, let us consider, given a sequence \(A\) of length \(N\), a simple problem of finding the minimum non-negative integer not contained in \(A\).

Then, the answer is obviously between \(0\) and \(N\), so we can safely ignore the negative elements and the elements greater than \(N\) in \(A\), as it does not affect the answer.

Based on this observation, we can solve the original problem too. Let us call a value important if we cannot ignore it. How many important values are there?

There are at most \(N\) values for \(i=1\), at most \(\lceil\frac{N}{2}\rceil\) values for \(i=2\), … so, by the harmonic series, there are \(\mathrm{O}(N\log N)\) important values in total.

Therefore, the sum of the answer is also about \(\mathrm{O}(N\log N)\). Therefore, it is fast enough to find the answer for each output in a linear time of the answer.

Specifically, for each operation, we can check if there is \(0\), there is \(1\), …. See the sample code for how to store the data.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(auto &v : a) cin >> v;
    vector<vector<int>> vals(m + 1);
    for(int i = 0; i < n; i++) {
        if(a[i] >= n) continue;
        int l = (a[i] >= 0 ? 1 : (-a[i] + i) / (i + 1));
        int r = min(m + 1, (n - a[i] + i) / (i + 1));
        for(int j = l; j < r; j++) {
            vals[j].push_back(a[i] + (i + 1) * j);
        }
    }
    for(int i = 1; i <= m; i++) {
        int sz = vals[i].size();
        vector<bool> exi(sz + 1);
        for(auto v : vals[i]) {
            if(v < sz) exi[v] = true;
        }
        int res = 0;
        while(exi[res]) res++;
        cout << res << endl;
    }
}