#include <bits/stdc++.h>
using namespace std;
const int pod = (1 << 20);
const int N = 4e5 + 100;
int n, m;
int h[N];
int a[N], b[N];
vector<int> val;
int daj(int x) {
  return (int)(lower_bound(val.begin(), val.end(), x) - val.begin());
}
struct tree {
  int t[2 * pod];
  void init() {
    for (int i = 1; i <= 2 * pod - 1; ++i) t[i] = 0;
  }
  void add(int x, int c) {
    x += pod;
    t[x] = max(t[x], c);
    x /= 2;
    while (x) {
      t[x] = max(t[2 * x], t[2 * x + 1]);
      x /= 2;
    }
  }
  int query(int l, int r) {
    int res = 0;
    r += 1;
    for (l += pod, r += pod; l < r; l /= 2, r /= 2) {
      if (l & 1) res = max(res, t[l++]);
      if (r & 1) res = max(res, t[--r]);
    }
    return res;
  }
} qw;
int ans[N], ans2[N];
vector<pair<int, int>> pr[N];
int sum[N];
int Lis[N];
void ad(int l, int r) {
  if (l > r) return;
  sum[l]++;
  sum[r + 1]--;
}
vector<pair<int, int>> qulewo[N], quprawo[N];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", h + i);
    val.push_back(h[i]);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", a + i, b + i);
    val.push_back(b[i]);
  }
  sort(val.begin(), val.end());
  val.erase(unique(val.begin(), val.end()), val.end());
  h[0] = -1;
  h[n + 1] = 1e9;
  int Maxlis = 0;
  for (int i = 1; i <= n; ++i) h[i] = daj(h[i]);
  for (int i = 1; i <= m; ++i) b[i] = daj(b[i]);
  qw.init();
  for (int i = 1; i <= n; ++i) {
    int z = 1 + qw.query(0, h[i] - 1);
    qw.add(h[i], z);
    Maxlis = max(Maxlis, z);
    Lis[i] = z;
  }
  for (int i = 1; i <= m; ++i) ans[i] = Maxlis - 1;
  qw.init();
  pr[0].push_back({n + 1, 0});
  for (int i = n; 1 <= i; --i) {
    int z = 1 + qw.query(h[i] + 1, pod - 1);
    qw.add(h[i], z);
    pr[z].push_back({i, 0});
  }
  for (int i = 0; i <= n; ++i) {
    reverse(pr[i].begin(), pr[i].end());
    for (int j = (int)pr[i].size() - 1; 0 <= j; --j) {
      pr[i][j].second = h[pr[i][j].first];
      if (j + 1 != (int)pr[i].size())
        pr[i][j].second = max(pr[i][j].second, pr[i][j + 1].second);
    }
  }
  qw.init();
  for (int i = 0; i <= n; ++i) {
    int r = Maxlis - Lis[i];
    int L = -1, R = (int)pr[r].size() - 1;
    while (L < R) {
      int M = (L + R + 1) / 2;
      if (pr[r][M].second > h[i])
        L = M;
      else
        R = M - 1;
    }
    if (0 <= L) ad(i + 1, pr[r][L].first - 1);
  }
  for (int i = 1; i <= n; ++i) sum[i] += sum[i - 1];
  for (int i = 1; i <= m; ++i) {
    if (sum[a[i]] > 0) ans[i] = Maxlis;
    qulewo[a[i] - 1].push_back({i, b[i] - 1});
    quprawo[a[i] + 1].push_back({i, b[i] + 1});
  }
  qw.init();
  for (int i = 1; i <= n; ++i) {
    int z = 1 + qw.query(0, h[i] - 1);
    qw.add(h[i], z);
    for (auto it : qulewo[i]) ans2[it.first] += qw.query(0, it.second);
  }
  qw.init();
  for (int i = n; 1 <= i; --i) {
    int z = 1 + qw.query(h[i] + 1, pod - 1);
    qw.add(h[i], z);
    for (auto it : quprawo[i]) ans2[it.first] += qw.query(it.second, pod - 1);
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", max(ans[i], ans2[i] + 1));
  return 0;
}
