#include <bits/stdc++.h>
template <typename T>
bool chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
bool chkmax(T &a, const T &b) {
  return b > a ? a = b, 1 : 0;
}
using namespace std;
int read() {
  int n = 0, p = 1;
  char ch;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') p = -1;
  for (; '0' <= ch && ch <= '9'; ch = getchar()) n = n * 10 + ch - '0';
  return n * p;
}
const int N = 4e5 + 5;
int n, m, q, ans, f[N], g[N], cnt[N], h[N], ps[N];
bool bz[N];
long long a[N], _a[N], c[N], mxv[N];
struct Q {
  int x, y, id;
} b[N];
bool cmp1(Q a, Q b) { return a.x < b.x; }
bool cmp2(Q a, Q b) { return a.x > b.x; }
int main() {
  n = read(), q = read();
  for (int i = (1); i <= (n); ++i) a[i] = read();
  for (int i = (1); i <= (n); ++i) {
    f[i] = lower_bound(c + 1, c + c[0] + 1, a[i]) - c;
    if (f[i] > c[0]) ++c[0];
    c[f[i]] = a[i];
  }
  ans = c[0];
  mxv[ans + 1] = 1e10;
  for (int i = (n); i >= (1); --i)
    if (a[i] < mxv[f[i] + 1]) {
      bz[i] = 1;
      chkmax(mxv[f[i]], a[i]);
    }
  for (int i = (1); i <= (n); ++i)
    if (bz[i]) ++cnt[f[i]];
  for (int i = (1); i <= (q); ++i)
    b[i].x = ps[i] = read(), b[i].y = read(), b[i].id = i;
  sort(b + 1, b + q + 1, cmp1);
  memset(c, -60, sizeof(c));
  m = 0;
  for (int i = 1, j = 1; i <= n; ++i) {
    for (; j <= q && b[j].x == i; ++j)
      h[b[j].id] = lower_bound(c + 1, c + m + 1, b[j].y) - c - 1;
    g[i] = lower_bound(c + 1, c + m + 1, a[i]) - c;
    if (g[i] > m) ++m;
    c[g[i]] = a[i];
  }
  sort(b + 1, b + q + 1, cmp2);
  memset(c, -60, sizeof(c));
  m = 0;
  for (int i = (1); i <= (n); ++i) _a[i] = -a[i];
  reverse(_a + 1, _a + n + 1);
  for (int i = 1, j = 1; i <= n; ++i) {
    for (; j <= q && b[j].x == n - i + 1; ++j)
      h[b[j].id] += lower_bound(c + 1, c + m + 1, -b[j].y) - c;
    g[i] = lower_bound(c + 1, c + m + 1, _a[i]) - c;
    if (g[i] > m) ++m;
    c[g[i]] = _a[i];
  }
  for (int i = (1); i <= (q); ++i) {
    int t = h[i];
    chkmax(t, (bz[ps[i]] && cnt[f[ps[i]]] == 1) ? ans - 1 : ans);
    printf("%d\n", t);
  }
  return 0;
}
