#include <bits/stdc++.h>
using namespace std;
int const M = 4e5 + 20;
int a[M], ans[M], l[M], r[M], ty[M], cnt[M], sv[M];
vector<pair<int, int> > qu[M];
int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= q; i++) {
    int ind, nu;
    cin >> ind >> nu;
    qu[ind].push_back(make_pair(nu, i));
    sv[i] = ind;
  }
  vector<int> lis;
  for (int i = 1; i <= n; i++) {
    qu[i].push_back(make_pair(a[i], 0));
    for (int j = 0; j < qu[i].size(); j++) {
      int now = qu[i][j].first;
      if (lis.size() == 0 || now > lis.back()) {
        ans[qu[i][j].second] = (int)lis.size() + 1;
      } else {
        int ind = lower_bound(lis.begin(), lis.end(), now) - lis.begin();
        ans[qu[i][j].second] = ind + 1;
      }
      if (j == (int)qu[i].size() - 1) {
        l[i] = ans[0];
        if (ans[0] == (int)lis.size() + 1)
          lis.push_back(a[i]);
        else
          lis[ans[0] - 1] = a[i];
      }
    }
  }
  int best = lis.size();
  lis.clear();
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < qu[i].size(); j++) {
      int now = qu[i][j].first;
      now = -now;
      if (lis.size() == 0 || now > lis.back()) {
        ans[qu[i][j].second] += (int)lis.size();
        if (j == (int)qu[i].size() - 1) {
          r[i] = (int)lis.size() + 1;
          lis.push_back(now);
        }
      } else {
        int ind = lower_bound(lis.begin(), lis.end(), now) - lis.begin();
        ans[qu[i][j].second] += ind;
        if (j == (int)qu[i].size() - 1) {
          r[i] = ind + 1;
          lis[ind] = now;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (l[i] + r[i] != best + 1) {
      ty[i] = 3;
    } else
      cnt[l[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    if (ty[i] != 3 && cnt[l[i]] > 1)
      ty[i] = 2;
    else if (ty[i] != 3)
      ty[i] = 1;
  }
  for (int i = 1; i <= q; i++) {
    int tmp = ans[i];
    if (ty[sv[i]] == 1)
      tmp = max(tmp, best - 1);
    else
      tmp = max(tmp, best);
    cout << tmp << "\n";
  }
}
