#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9;
int n, q;
int a[400005];
struct rmq {
  int tree[1050000], lim;
  void init(int n) {
    memset(tree, 0, sizeof(tree));
    for (lim = 1; lim <= n; lim <<= 1)
      ;
  }
  void add(int x, int v) {
    x += lim;
    tree[x] = max(tree[x], v);
    while (x > 1) {
      x >>= 1;
      tree[x] = max(tree[2 * x], tree[2 * x + 1]);
    }
  }
  int query(int s, int e) {
    s += lim;
    e += lim;
    int ret = 0;
    while (s < e) {
      if (s % 2 == 1) ret = max(ret, tree[s++]);
      if (e % 2 == 0) ret = max(ret, tree[e--]);
      s >>= 1;
      e >>= 1;
    }
    if (s == e) ret = max(ret, tree[s]);
    return ret;
  }
} rmq;
int dpl[400005], dpr[400005], lis;
int cnt[400005];
bool check_indep(int x) {
  return cnt[dpr[x]] != 1 || dpl[x] + dpr[x] != lis + 1;
}
int is_indep[400005];
int aux[400005], ret[400005];
struct query {
  int x, y, idx;
  bool operator<(const query &q) const { return x < q.x; }
};
int main() {
  scanf("%d %d", &n, &q);
  vector<int> v;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    v.push_back(a[i]);
  }
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
  }
  rmq.init(n);
  for (int i = 1; i <= n; i++) {
    dpl[i] = rmq.query(1, a[i] - 1) + 1;
    rmq.add(a[i], dpl[i]);
  }
  rmq.init(n);
  for (int i = n; i; i--) {
    dpr[i] = rmq.query(a[i] + 1, n) + 1;
    rmq.add(a[i], dpr[i]);
  }
  for (int i = 1; i <= n; i++) {
    lis = max(lis, dpl[i]);
  }
  for (int i = 1; i <= n; i++) {
    if (dpl[i] + dpr[i] == lis + 1) {
      cnt[dpr[i]]++;
    }
  }
  for (int i = 1; i <= n; i++) {
    is_indep[i] = check_indep(i);
  }
  vector<query> qr;
  for (int i = 0; i < q; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    if (is_indep[x]) {
      ret[i] = lis;
    } else
      ret[i] = lis - 1;
    qr.push_back({x, y, i});
  }
  sort(qr.begin(), qr.end());
  rmq.init(n);
  int pnt = 1;
  for (int i = 0; i < q; i++) {
    while (pnt <= n && pnt < qr[i].x) {
      rmq.add(a[pnt], dpl[pnt]);
      pnt++;
    }
    int sy = lower_bound(v.begin(), v.end(), qr[i].y) - v.begin();
    aux[qr[i].idx] += rmq.query(1, sy);
  }
  pnt = n;
  rmq.init(n);
  for (int i = q - 1; i >= 0; i--) {
    while (pnt && pnt > qr[i].x) {
      rmq.add(a[pnt], dpr[pnt]);
      pnt--;
    }
    int ey = upper_bound(v.begin(), v.end(), qr[i].y) - v.begin() + 1;
    aux[qr[i].idx] += rmq.query(ey, n);
  }
  for (int i = 0; i < q; i++) {
    ret[i] = max(ret[i], aux[i] + 1);
    printf("%d\n", ret[i]);
  }
}
