#include <bits/stdc++.h>
using namespace std;
int add(int a, int b) {
  a += b;
  if (a >= 1000000003) a -= 1000000003;
  return a;
}
pair<int, int> I = make_pair(0, 0);
struct nd {
  pair<int, int> v;
  nd *l, *r;
  nd() {
    v = I;
    l = r = 0;
  }
};
pair<int, int> op(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first == b.first)
    return make_pair(a.first, add(a.second, b.second));
  else
    return max(a, b);
}
pair<int, int> q(nd *i, int rs, int re, int qs, int qe) {
  if (qs == qe) return I;
  if (i == 0) return I;
  if (rs == qs && re == qe)
    return i->v;
  else {
    int md = (rs + re) / 2;
    pair<int, int> r = I;
    if (qs < md) r = op(r, q(i->l, rs, md, qs, min(qe, md)));
    if (qe > md) r = op(r, q(i->r, md, re, max(qs, md), qe));
    return r;
  }
}
nd *u(nd *i, int rs, int re, int qi, pair<int, int> qv) {
  nd *res = i;
  if (rs + 1 == re)
    res->v = op(res->v, qv);
  else {
    if (i->l == 0) {
      i->l = new nd;
      i->r = new nd;
    }
    int md = (rs + re) / 2;
    if (qi < md)
      res->l = u(i->l, rs, md, qi, qv);
    else
      res->r = u(i->r, md, re, qi, qv);
    res->v = op(res->l->v, res->r->v);
  }
  return res;
}
int n, Q;
int h[400005];
nd *l[400005];
nd *r[400005];
pair<int, int> nl[400005];
int nw[400005];
int qa[400005];
int qb[400005];
int ans[400005];
int cc[800010], C;
vector<pair<int, int> > ql[400005];
vector<pair<int, int> > qr[400005];
void stmc() {
  scanf("%d %d", &n, &Q);
  for (int i = (0); i < (n); i++) {
    scanf("%d ", h + i);
    cc[C++] = h[i];
  }
  for (int i = (0); i < (Q); i++) {
    scanf("%d %d", qa + i, qb + i);
    qa[i]--;
    cc[C++] = qb[i];
  }
  sort(cc, cc + C);
  C = unique(cc, cc + C) - cc;
  for (int i = (0); i < (n); i++) h[i] = lower_bound(cc, cc + C, h[i]) - cc;
  for (int i = (0); i < (Q); i++) qb[i] = lower_bound(cc, cc + C, qb[i]) - cc;
}
void lpc(int i) {
  for (auto p : ql[i]) {
    ans[p.second] += q(l[i], 0, 800010, 0, p.first).first;
  }
}
void rpc(int i) {
  for (auto p : qr[i]) {
    ans[p.second] += q(r[i], 0, 800010, p.first + 1, 800010).first;
  }
}
int main() {
  stmc();
  for (int z = (0); z < (Q); z++) {
    int a = qa[z], b = qb[z];
    ql[a].push_back(make_pair(b, z));
    qr[n - a - 1].push_back(make_pair(b, z));
  }
  pair<int, int> bl = I;
  l[0] = new nd;
  lpc(0);
  for (int i = (0); i < (n); i++) {
    pair<int, int> t = q(l[i], 0, 800010, 0, h[i]);
    t.first++;
    t = op(t, make_pair(1, 1));
    bl = op(bl, t);
    nl[i] = t;
    l[i + 1] = u(l[i], 0, 800010, h[i], t);
    lpc(i + 1);
  }
  r[0] = new nd;
  rpc(0);
  for (int i = (0); i < (n); i++) {
    pair<int, int> t = q(r[i], 0, 800010, h[n - 1 - i] + 1, 800010);
    t.first++;
    t = op(t, make_pair(1, 1));
    if (nl[n - i - 1].first + t.first - 1 == bl.first) {
      nw[n - 1 - i] = nl[n - 1 - i].second * 1ll * t.second % 1000000003;
    } else {
      nw[n - 1 - i] = -1;
    }
    r[i + 1] = u(r[i], 0, 800010, h[n - 1 - i], t);
    rpc(i + 1);
  }
  for (int z = (0); z < (Q); z++) {
    int a = qa[z], b = qb[z];
    int bwo = -1;
    if (nw[a] != bl.second)
      bwo = bl.first;
    else
      bwo = bl.first - 1;
    int bw = ans[z] + 1;
    printf("%d\n", max(bwo, bw));
  }
}
