#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 400007;
const int M = 1 << 20;
int D[2 * M];
void insert(int x, int w) {
  x += M;
  D[x] = max(D[x], w);
  x /= 2;
  while (x > 0) {
    D[x] = max(D[2 * x], D[2 * x + 1]);
    x /= 2;
  }
}
int query(int a, int b) {
  a += M;
  b += M;
  int res = max(D[a], D[b]);
  while (a / 2 != b / 2) {
    if (a % 2 == 0) res = max(res, D[a + 1]);
    if (b % 2 == 1) res = max(res, D[b - 1]);
    a /= 2;
    b /= 2;
  }
  return res;
}
int h[N];
vector<int> wor[N];
int qh[N];
int qa[N];
int wqpre[N];
int wqsuf[N];
int pre[N];
int suf[N];
int wyn[N];
int minpoz[M];
int przedzialy[N];
void dodaj_przedzial(int a, int b) {
  if (a <= b) {
    przedzialy[a]++;
    przedzialy[b + 1]--;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  vector<pair<int, int> > pnum;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    h[i] = x;
    pnum.push_back(make_pair(x, i));
  }
  for (int i = 1; i <= m; ++i) {
    int x;
    cin >> qa[i] >> x;
    qh[i] = x;
    wor[qa[i]].push_back(i);
    pnum.push_back(make_pair(x, -i));
  }
  sort(pnum.begin(), pnum.end());
  int zp = 1;
  for (int i = 0; i < pnum.size(); ++i) {
    if (i + 1 < pnum.size() && pnum[i + 1].first != pnum[i].first)
      pnum[i].first = zp++;
    else
      pnum[i].first = zp;
    if (pnum[i].second > 0)
      h[pnum[i].second] = pnum[i].first;
    else
      qh[-pnum[i].second] = pnum[i].first;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < wor[i].size(); ++j)
      wqpre[wor[i][j]] = query(0, qh[wor[i][j]] - 1) + 1;
    pre[i] = query(0, h[i] - 1) + 1;
    insert(h[i], pre[i]);
  }
  for (int i = 0; i < 2 * M; ++i) D[i] = 0;
  for (int i = n; i > 0; --i) {
    for (int j = 0; j < wor[i].size(); ++j)
      wqsuf[wor[i][j]] = query(qh[wor[i][j]] + 1, M - 1) + 1;
    suf[i] = query(h[i] + 1, M - 1) + 1;
    insert(h[i], suf[i]);
  }
  for (int i = 1; i <= m; ++i) wyn[i] = wqpre[i] + wqsuf[i] - 1;
  int S = 0;
  for (int i = 1; i <= n; ++i) S = max(S, pre[i]);
  vector<pair<int, int> > tt;
  for (int i = 1; i <= n; ++i) tt.push_back(make_pair(h[i], i));
  tt.push_back(make_pair(0, 0));
  tt.push_back(make_pair(1e9, n + 1));
  sort(tt.begin(), tt.end());
  for (int i = 0; i < M; ++i) minpoz[i] = 1e9;
  for (int i = 0; i < tt.size(); ++i) {
    if (i + 1 == n || tt[i].first != tt[i + 1].first) {
      int j = i;
      while (j > 0 && tt[j - 1].first == tt[i].first) j--;
      for (int z = j; z <= i; ++z) {
        dodaj_przedzial(minpoz[S - suf[tt[z].second]] + 1, tt[z].second - 1);
      }
      for (int z = j; z <= i; ++z) {
        minpoz[pre[tt[z].second]] =
            min(minpoz[pre[tt[z].second]], tt[z].second);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    przedzialy[i] += przedzialy[i - 1];
    if (przedzialy[i] > 0) {
      for (int j = 0; j < wor[i].size(); ++j)
        wyn[wor[i][j]] = max(wyn[wor[i][j]], S);
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (wyn[i] < S)
      cout << S - 1 << endl;
    else
      cout << wyn[i] << '\n';
  }
  return 0;
}
