#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 10;
const int INF = 2e9;
struct query {
  int x, h;
  int i;
  int pf, sf;
  void read(int id) {
    scanf("%d %d", &x, &h);
    x--;
    i = id;
  }
};
bool operator<(query q1, query q2) { return q1.x < q2.x; }
int N, M;
query Q[MAXN];
int A[MAXN];
int pref[MAXN], suff[MAXN], L;
int seq[MAXN];
int getseq(int h) { return lower_bound(seq, seq + N, h) - seq; }
int num[MAXN];
bool req[MAXN];
int ans[MAXN];
int main() {
  scanf("%d %d", &N, &M);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  for (int i = 0; i < M; i++) {
    Q[i].read(i);
  }
  sort(Q, Q + M);
  fill_n(seq, N, INF);
  for (int i = 0, j = 0; i < N; i++) {
    for (; j < M && Q[j].x == i; j++) {
      Q[j].pf = getseq(Q[j].h);
    }
    pref[i] = getseq(A[i]);
    seq[pref[i]] = A[i];
    L = max(L, pref[i] + 1);
  }
  fill_n(seq, N, INF);
  for (int i = N - 1, j = M - 1; i >= 0; i--) {
    for (; j >= 0 && Q[j].x == i; j--) {
      Q[j].sf = getseq(-Q[j].h);
    }
    suff[i] = getseq(-A[i]);
    seq[suff[i]] = -A[i];
  }
  for (int i = 0; i < N; i++) {
    if (pref[i] + suff[i] + 1 == L) {
      num[pref[i]]++;
    }
  }
  for (int i = 0; i < N; i++) {
    req[i] = (pref[i] + suff[i] + 1 == L && num[pref[i]] == 1);
  }
  for (int i = 0; i < M; i++) {
    ans[Q[i].i] = max(Q[i].pf + Q[i].sf + 1, L - req[Q[i].x]);
  }
  for (int i = 0; i < M; i++) {
    printf("%d\n", ans[i]);
  }
}
