Ankit and Cricket

Let us call an integer good if it is different from either of B1,B2,B3,…,Bn.

For each ii, find the number of good integers less than or equal to Bi​ and record them as Ci.

Then, the Ath smallest good integer can be found as follows:

  • If Cn<A
    • The answer is always greater than Bn. Since every integer greater than Bn​ is a good integer, the answer is Bn+(A-Cn)
  • If Cn >= A
    • Find with binary search the minimum i such that Ci>=A, then the answer is greater than Bi -1 and less than Bi​ (where we assume A0=0). Since every integer greater than **B(i-1)**​ and less than Bi​ is a good integer, the answer is (Bi-1)-(Ci-A) that is, Ci-A elements before Bi-1

The complexity is O(N+QlogN)

Code(C++):

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

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for (auto& x : A) {
        cin >> x;
    }
    vector<long long> low(N);
    for (int i = 0; i < N; ++i) {
        low[i] = A[i] - (i + 1);
    }
    while (Q--) {
        long long K;
        cin >> K;
        const int idx = lower_bound(low.begin(), low.end(), K) - low.begin();
        if (idx == N) {
            cout << A[N - 1] + (K - low[N - 1]) << '\n';
        } else {
            cout << A[idx] - (low[idx] - K + 1) << '\n';
        }
    }
    return 0;
}