#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int inf = INT_MAX;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<int> a(n), dp_right(n + 1), dp_left(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp_right[i + 1] = inf + 1;
        dp_left[i + 1] = inf;
    }
    dp_right[0] = -inf;
    dp_left[0] = -inf;
    vector<pair<int, int>> rebuild(n, {-1, -1});
    for (int i = n - 1; i >= 0; i--) {
        int j = upper_bound(all(dp_right), -a[i]) - dp_right.begin();
        if (dp_right[j - 1] < -a[i]) {
            rebuild[i] = {j, dp_right[j]};
            dp_right[j] = -a[i];
        }
    }
    vector<vector<pair<int, int>>> q(n);
    for (int i = 0; i < m; i++) {
        int pos, val; cin >> pos >> val;
        pos--;
        q[pos].push_back({val, i});
    }
    vector<int> res(m);
    for (int i = 0; i < n; i++) {
        if (rebuild[i] != pair<int, int>{-1, -1}) {
            dp_right[rebuild[i].first] = rebuild[i].second;
        }
        for (int k = 0; k < (int)q[i].size(); k++) {
            pair<int, int> rollback = {-1, -1};
            int v, t; v = q[i][k].first, t = q[i][k].second;
            int j = upper_bound(all(dp_left), v) - dp_left.begin();
            //if(dp_left[l - 1] == v) { l--; }
            if (dp_left[j - 1] < v) {
                rollback = { j, dp_left[j]};
                dp_left[j] = v;
            }

            auto count = [&](int ind) {
                int val_ind = dp_left[ind];
                int rs = upper_bound(all(dp_right), -val_ind) - dp_right.begin();
                if (dp_right[rs - 1] == -val_ind) {
                    rs--;
                }
                return rs + ind - 1;
            };
            int l = 1, r = upper_bound(all(dp_left), inf - 1) - dp_left.begin() - 1;
            assert(l <= r);
            while (r - l > 350) {
                int tl = l + (r - l) / 3;
                int tr = r - (r - l) / 3;
                if (count(tl) <= count(tr)) {
                    l = tl;
                }
                else {
                    r = tr;
                }
            }
            //int r = upper_bound(all(dp_right), -v) - dp_right.begin();
            //if(dp_right[r - 1] == v) { r--; }
            //res[t] = r + l - 1;
            for (int b = l; b <= r; b++) {
                res[t] = max(res[t], count(b));
            }
            res[t] = max(res[t], count(0));
            if (rollback != pair<int, int>{-1, -1}) {
                dp_left[rollback.first] = rollback.second;
            }
        }

        int j = upper_bound(all(dp_left), a[i]) - dp_left.begin();
        if (dp_left[j - 1] < a[i]) {
            dp_left[j] = a[i];
        }
    }
    for (int i = 0; i < m; i++) {
        cout << res[i] << '\n';
    }
}