Consider the following DP (Dynamic Programming) that is typically used to find the length of a LIS (Longest monotonically Increasing Subsequence). (We do not introduce the transitions or the validity of this DP here.)

• Inspect \(A_i\) in the order of \(i=1,2\dots,N\) to update the following DP table in-place.
  • \(\mathrm{dp}_j\ (1\leq j\leq N)=\) (the smallest value of the final term of a length-\(j\) subsequence that can be extracted from the elements so far, or \(\infty\) if there is no such subsequence).

Considering the definition of the DP above, the answer to query \(k\) turns out to be equal to:

• the maximum \(j\) such that \(\mathrm{dp}_j \leq X_k\) in the DP table when inspecting up to \(i=R_k\).

Therefore, one can perform the DP above, while for each step \(i\), finding the answer for all queries \(k\) with \(i=R_k\) using binary search.

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 100;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i: a) cin >> i;
    vector<vector<pair<int, int>>> qs(n);
    for (int i = 0; i < q; i++) {
        int r, x;
        cin >> r >> x;
        qs[--r].emplace_back(i, x);
    }
    vector<int> ans(q);
    vector<int> dp(n, inf);
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        *it = a[i];
        for (auto [id, x]: qs[i]) {
            ans[id] = upper_bound(dp.begin(), dp.end(), x) - dp.begin();
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}