#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
const int inf = 1e9 + 10;
int ch_idx[maxn], ch_val[maxn], lis[maxn], lds[maxn];
int a[maxn], b[maxn], pre[maxn], fol[maxn];
int cc[maxn];
vector<int> que[maxn];
void LIS(int n) {
  int g[maxn];
  for (int i = 1; i <= n; i++) g[i] = inf;
  for (int i = 1; i <= n; i++) {
    int k = (int)(lower_bound(g + 1, g + n + 1, a[i]) - g);
    for (int j = 0; j < que[i].size(); j++) {
      int op_id = que[i][j];
      pre[op_id] = (int)(lower_bound(g + 1, g + n + 1, ch_val[op_id]) - g);
    }
    lis[i] = k;
    g[k] = a[i];
  }
}
void LDS(int n) {
  int g[maxn];
  for (int i = 1; i <= n; i++) g[i] = 0;
  for (int i = 1; i <= n; i++) {
    int k = (int)(lower_bound(g + 1, g + n + 1, b[i]) - g);
    for (int j = 0; j < que[n - i + 1].size(); j++) {
      int op_id = que[n - i + 1][j];
      fol[op_id] = (int)(lower_bound(g + 1, g + n + 1, -ch_val[op_id]) - g);
    }
    lds[i] = k;
    g[k] = b[i];
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[n - i + 1] = -a[i];
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &ch_idx[i], &ch_val[i]);
    que[ch_idx[i]].push_back(i);
  }
  LIS(n);
  LDS(n);
  int maxl = 0;
  for (int i = 1; i <= n; i++) maxl = max(maxl, lis[i]);
  for (int i = 1; i <= n; i++)
    if (lis[i] + lds[n - i + 1] - 1 == maxl) ++cc[lis[i]];
  for (int i = 0; i < m; i++) {
    int v = maxl, idx = ch_idx[i];
    if (lis[idx] + lds[n - idx + 1] - 1 == maxl && cc[lis[idx]] == 1) --v;
    printf("%d\n", max(v, pre[i] + fol[i] - 1));
  }
  return 0;
}
