まず、長さ \(N\) の数列 \(A\) が与えられるので \(A\) に含まれない最小の非負整数を求めるという、より単純な問題について考えます。

このとき、 答えは明らかに \(0\) 以上 \(N\) 以下であることから、 \(A\) に含まれる要素のうち負の要素及び \(N\) 以上の要素は答えに影響がないので無視して構わないことがわかります。

この観察を用いると、もともとの問題についても解くことができます。無視してはいけない値を大事な値と呼ぶことにします。大事な値が合計で何個あるかを分析します。

すると、\(i=1\) が大事な値となる個数は最大で \(N\) 個、\(i=2\) では最大で \(\lceil\frac{N}{2}\rceil\) 個、… となることから、調和級数より大事な値は \(\mathrm{O}(N\log N)\) 個しか存在しないことがわかります。

よって出力する答えの合計も \(\mathrm{O}(N\log N)\) 程度であることがわかります。このことから、各出力について答えの線形のオーダーで答えを求めても十分高速です。

具体的には、各操作について、\(0\) が存在するか、 \(1\) が存在するか、…を判定することを繰り返せば良いです。データの持ち方については、実装例を参考にしてください。

実装例(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;
    }
}