#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
const int inf = ~0u >> 2;
int a[N];
struct Q {
  int val, id;
  Q() {}
  Q(int b, int c) { val = b, id = c; }
};
vector<Q> qry[N];
int lsa[N], lsb[N];
int ansla[N], anslb[N];
int ans[N];
int p[N], pcnt;
int n, m;
int cs[N];
bool ok[N];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 1; i <= m; ++i) {
    int pos, val;
    scanf("%d%d", &pos, &val);
    qry[pos].push_back(Q(val, i));
  }
  p[0] = -inf, pcnt = 1;
  for (int i = 1; i <= n; ++i) {
    for (int k = qry[i].size() - 1; k >= 0; --k) {
      int pos = lower_bound(p, p + pcnt, qry[i][k].val) - p;
      ansla[qry[i][k].id] = pos;
    }
    int pos = lower_bound(p, p + pcnt, a[i]) - p;
    lsa[i] = pos;
    p[pos] = a[i];
    if (pos == pcnt) ++pcnt;
  }
  int lis = pcnt - 1;
  p[0] = -inf, pcnt = 1;
  for (int i = n; i >= 1; --i) {
    for (int k = qry[i].size() - 1; k >= 0; --k) {
      int pos = lower_bound(p, p + pcnt, -qry[i][k].val) - p;
      anslb[qry[i][k].id] = pos;
    }
    int pos = lower_bound(p, p + pcnt, -a[i]) - p;
    lsb[i] = pos;
    p[pos] = -a[i];
    if (pos == pcnt) ++pcnt;
  }
  memset(cs, -1, sizeof(cs));
  for (int i = 1; i <= n; ++i) {
    if (lsa[i] + lsb[i] == lis + 1) {
      if (cs[lsa[i]] == -1)
        cs[lsa[i]] = i;
      else
        cs[lsa[i]] = -2;
    }
  }
  for (int i = 1; i <= lis; ++i)
    if (cs[i] > 0) ok[cs[i]] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int k = 0; k < qry[i].size(); ++k) {
      ans[qry[i][k].id] = max(ok[i] ? lis - 1 : lis,
                              ansla[qry[i][k].id] + anslb[qry[i][k].id] - 1);
    }
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
}
