#include <bits/stdc++.h>
using namespace std;
const int N = 400010, M = 2222222;
int n, m, i, j, a[N], cnt, b[N << 1], e[N][2], f[N], g[N], ans, c[N], must[N],
    v[M], fin[N], L[N], R[N];
int G[N], V[N], NXT[N];
inline void edge(int x, int y, int z) {
  V[z] = y;
  NXT[z] = G[x];
  G[x] = z;
}
inline int lower(int x) {
  int l = 1, r = cnt, t, mid;
  while (l <= r)
    if (b[mid = (l + r) >> 1] <= x)
      l = (t = mid) + 1;
    else
      r = mid - 1;
  return t;
}
void build(int x, int a, int b) {
  v[x] = 0;
  if (a == b) return;
  int mid = (a + b) >> 1;
  build(x << 1, a, mid), build(x << 1 | 1, mid + 1, b);
}
void add(int x, int a, int b, int c, int p) {
  v[x] = max(v[x], p);
  if (a == b) return;
  int mid = (a + b) >> 1;
  if (c <= mid)
    add(x << 1, a, mid, c, p);
  else
    add(x << 1 | 1, mid + 1, b, c, p);
}
int ask(int x, int a, int b, int c, int d) {
  if (c > d) return 0;
  if (c <= a && b <= d) return v[x];
  int mid = (a + b) >> 1, t = 0;
  if (c <= mid) t = ask(x << 1, a, mid, c, d);
  if (d > mid) t = max(t, ask(x << 1 | 1, mid + 1, b, c, d));
  return t;
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]), b[++cnt] = a[i];
  for (i = 1; i <= m; i++)
    scanf("%d%d", &e[i][0], &e[i][1]), b[++cnt] = e[i][1];
  sort(b + 1, b + cnt + 1);
  for (i = 1; i <= n; i++) a[i] = lower(a[i]);
  build(1, 1, cnt);
  for (i = 1; i <= n; i++) {
    f[i] = ask(1, 1, cnt, 1, a[i] - 1) + 1;
    add(1, 1, cnt, a[i], f[i]);
  }
  build(1, 1, cnt);
  for (i = n; i; i--) {
    g[i] = ask(1, 1, cnt, a[i] + 1, cnt) + 1;
    add(1, 1, cnt, a[i], g[i]);
  }
  for (i = 1; i <= n; i++)
    if (f[i] + g[i] - 1 > ans) ans = f[i] + g[i] - 1;
  for (i = 1; i <= n; i++)
    if (f[i] + g[i] - 1 == ans) c[f[i]]++;
  for (i = 1; i <= n; i++)
    if (f[i] + g[i] - 1 == ans && c[f[i]] == 1) must[i] = 1;
  for (i = 1; i <= m; i++) {
    fin[i] = ans;
    if (must[e[i][0]]) fin[i]--;
  }
  for (i = 1; i <= m; i++) edge(e[i][0], lower(e[i][1]), i);
  build(1, 1, cnt);
  for (i = 1; i <= n; i++) {
    for (j = G[i]; j; j = NXT[j]) L[j] = ask(1, 1, cnt, 1, V[j] - 1);
    add(1, 1, cnt, a[i], f[i]);
  }
  build(1, 1, cnt);
  for (i = n; i; i--) {
    for (j = G[i]; j; j = NXT[j]) R[j] = ask(1, 1, cnt, V[j] + 1, cnt);
    add(1, 1, cnt, a[i], g[i]);
  }
  for (i = 1; i <= m; i++) printf("%d\n", max(L[i] + R[i] + 1, fin[i]));
  return 0;
}
