#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const long long N = 800010;
struct data {
  long long id, x, v, pre, nxt;
} ask[N];
long long c[N], h[N], pre[N], nxt[N], q[N], kkk[N], n, m, tot, ans, answ[N];
bool cmp(data a, data b) { return a.x < b.x; }
long long qqq(long long x) {
  long long ans = 0;
  for (; x; x -= x & -x) ans = max(ans, c[x]);
  return ans;
}
long long QQQ(long long x) {
  long long ans = 0;
  for (; x <= tot; x += x & -x) ans = max(ans, c[x]);
  return ans;
}
void add(long long x, long long v) {
  for (; x <= tot; x += x & -x) c[x] = max(c[x], v);
}
void ADD(long long x, long long v) {
  for (; x; x -= x & -x) c[x] = max(c[x], v);
}
int main() {
  n = read();
  m = read();
  for (long long i = 1; i <= n; ++i) q[++tot] = h[i] = read();
  for (long long i = 1; i <= m; ++i)
    ask[i].id = i, ask[i].x = read(), ask[i].v = q[++tot] = read();
  sort(q + 1, q + tot + 1);
  tot = unique(q + 1, q + tot + 1) - q - 1;
  for (long long i = 1; i <= n; ++i)
    h[i] = lower_bound(q + 1, q + tot + 1, h[i]) - q;
  for (long long i = 1; i <= m; ++i)
    ask[i].v = lower_bound(q + 1, q + tot + 1, ask[i].v) - q;
  long long j = 0;
  sort(ask + 1, ask + m + 1, cmp);
  for (long long i = 1; i <= n; ++i) {
    pre[i] = qqq(h[i] - 1) + 1;
    while (ask[j + 1].x == i) {
      ++j;
      ask[j].pre = qqq(ask[j].v - 1) + 1;
    }
    add(h[i], pre[i]);
  }
  memset(c, 0, sizeof c);
  j = m + 1;
  for (long long i = n; i >= 1; --i) {
    nxt[i] = QQQ(h[i] + 1) + 1;
    ans = max(ans, nxt[i]);
    while (ask[j - 1].x == i) {
      --j;
      ask[j].nxt = QQQ(ask[j].v + 1) + 1;
    }
    ADD(h[i], nxt[i]);
  }
  for (long long i = 1; i <= n; ++i)
    if (pre[i] + nxt[i] == ans + 1) kkk[pre[i]]++;
  for (long long i = 1; i <= m; ++i) {
    long long ans1 = ask[i].pre + ask[i].nxt - 1,
              ans2 = (pre[ask[i].x] + nxt[ask[i].x] != ans + 1) ||
                             (kkk[pre[ask[i].x]] != 1)
                         ? ans
                         : ans - 1;
    answ[ask[i].id] = max(ans1, ans2);
  }
  for (long long i = 1; i <= m; ++i) writeln(answ[i]);
}
