#include <bits/stdc++.h>
using namespace std;
const int maxn = 800050;
const int maxm = maxn * 22;
int val[maxn], a[maxn], ql, qr, _v, p;
int ai[maxn], bi[maxn], tot, n, m;
int pos[maxn], num[maxn];
struct segtree {
  int maxv[maxm], LC[maxm], RC[maxm];
  int root[maxn];
  void ins(int q, int &o, int l, int r) {
    o = ++tot;
    LC[o] = LC[q];
    RC[o] = RC[q];
    maxv[o] = maxv[q];
    if (l == r) {
      maxv[o] = max(maxv[o], _v);
      return;
    }
    int m = (l + r >> 1);
    if (p <= m)
      ins(LC[q], LC[o], l, m);
    else
      ins(RC[q], RC[o], m + 1, r);
    maxv[o] = max(maxv[LC[o]], maxv[RC[o]]);
  }
  void query(int o, int l, int r) {
    if (ql <= l && r <= qr) {
      _v = max(_v, maxv[o]);
      return;
    }
    int m = (l + r >> 1);
    if (ql <= m) query(LC[o], l, m);
    if (qr > m) query(RC[o], m + 1, r);
  }
} R;
int maxv[maxn * 4], id[maxn], ans[maxn];
bool cmp(const int &a, const int &b) { return ai[a] < ai[b]; }
void ins(int o, int l, int r) {
  if (l == r) {
    maxv[o] = max(maxv[o], _v);
    return;
  }
  int m = (l + r >> 1);
  if (p <= m)
    ins((o << 1), l, m);
  else
    ins((o << 1 | 1), m + 1, r);
  maxv[o] = max(maxv[(o << 1)], maxv[(o << 1 | 1)]);
}
void query(int o, int l, int r) {
  if (ql <= l && r <= qr) {
    _v = max(_v, maxv[o]);
    return;
  }
  int m = (l + r >> 1);
  if (ql <= m) query((o << 1), l, m);
  if (qr > m) query((o << 1 | 1), m + 1, r);
}
int main() {
  scanf("%d%d", &n, &m);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    val[cnt++] = a[i];
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &ai[i], &bi[i]);
    val[cnt++] = bi[i];
    id[i] = i;
  }
  sort(val, val + cnt);
  sort(id + 1, id + m + 1, cmp);
  cnt = unique(val, val + cnt) - val;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(val, val + cnt, a[i]) - val + 1;
  for (int i = 1; i <= m; i++)
    bi[i] = lower_bound(val, val + cnt, bi[i]) - val + 1;
  int maxl = 0;
  for (int i = n; i >= 1; i--) {
    ql = a[i] + 1;
    qr = cnt;
    _v = 0;
    if (ql <= qr) R.query(R.root[i + 1], 1, cnt);
    p = a[i];
    _v++;
    maxl = max(maxl, _v);
    R.ins(R.root[i + 1], R.root[i], 1, cnt);
  }
  for (int i = 1; i <= n; i++) {
    ql = 1;
    qr = a[i] - 1;
    _v = 0;
    if (ql <= qr) query(1, 1, cnt);
    p = a[i];
    _v++;
    ins(1, 1, cnt);
    int len = _v;
    ql = a[i] + 1;
    qr = cnt;
    _v = 0;
    if (ql <= qr) R.query(R.root[i + 1], 1, cnt);
    if (len + _v == maxl) {
      num[len]++;
      pos[i] = len;
    }
  }
  memset(maxv, 0, sizeof maxv);
  for (int k = 1, j = 1; k <= m; k++) {
    int i = id[k], tmpm = maxl - 1;
    if (pos[ai[i]] == 0 || num[pos[ai[i]]] != 1) {
      tmpm++;
    }
    while (j < ai[i]) {
      ql = 1;
      qr = a[j] - 1;
      _v = 0;
      if (ql <= qr) query(1, 1, cnt);
      p = a[j];
      _v++;
      ins(1, 1, cnt);
      j++;
    }
    ans[i] = 1;
    ql = 1;
    qr = bi[i] - 1;
    _v = 0;
    if (ql <= qr) query(1, 1, cnt);
    ans[i] += _v;
    ql = bi[i] + 1;
    qr = cnt;
    _v = 0;
    if (ql <= qr) R.query(R.root[ai[i] + 1], 1, cnt);
    ans[i] += _v;
    ans[i] = max(ans[i], tmpm);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
