#include <bits/stdc++.h>
using namespace std;
struct Q {
  int id, pos, val;
  bool operator<(Q one) const { return pos < one.pos; }
} q[400010];
int a[400010], b[400010], c[400010], d[400010], ans[400010];
bool isok[400010];
int n, m;
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &q[i].pos, &q[i].val);
    q[i].pos--;
    q[i].id = i;
  }
  sort(q, q + m);
  int cnt = 0, len = 0;
  for (int i = 0; i < n; i++) {
    int index;
    while (cnt < m && q[cnt].pos == i) {
      index = lower_bound(b, b + len, q[cnt].val) - b;
      ans[q[cnt].id] = index + 1;
      cnt++;
    }
    index = lower_bound(b, b + len, a[i]) - b;
    b[index] = a[i];
    c[i] = index;
    if (index == len) len++;
  }
  int mx = len;
  cnt = m - 1, len = 0;
  memset(d, -1, sizeof(d));
  for (int i = n - 1; i > -1; i--) {
    int index;
    while (cnt > -1 && q[cnt].pos == i) {
      index = lower_bound(b, b + len, -q[cnt].val) - b;
      ans[q[cnt].id] += index;
      cnt--;
    }
    index = lower_bound(b, b + len, -a[i]) - b;
    b[index] = -a[i];
    if (index + c[i] + 1 == mx) {
      if (d[c[i]] != -1)
        isok[d[c[i]]] = isok[i] = 0;
      else {
        d[c[i]] = i;
        isok[i] = 1;
      }
    }
    if (index == len) len++;
  }
  for (int i = 0; i < m; i++)
    ans[q[i].id] = max(ans[q[i].id], isok[q[i].pos] ? mx - 1 : mx);
  for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
}
