#include <bits/stdc++.h>
using namespace std;
int n, m, h[400010], a[400010], b[400010], ls[800010], End;
inline int lowbit(int x) { return x & (-x); }
class tree {
 public:
  int dat[800010];
  void clear() { memset(dat, 0, sizeof(dat)); }
  void modify(int p, int v) {
    for (; p <= End; p += lowbit(p)) dat[p] = max(dat[p], v);
  }
  int query(int p) {
    int ret = 0;
    for (; p; p -= lowbit(p)) ret = max(ret, dat[p]);
    return ret;
  }
} T1;
class tree2 {
 public:
  int dat[800010];
  void clear() { memset(dat, 0, sizeof(dat)); }
  void modify(int p, int v) {
    for (; p; p -= lowbit(p)) dat[p] = max(dat[p], v);
  }
  int query(int p) {
    int ret = 0;
    for (; p <= End; p += lowbit(p)) ret = max(ret, dat[p]);
    return ret;
  }
} T2;
int pre[400010], suf[400010], f0[400010], g0[400010];
bool ok[400010];
vector<pair<int, int> > p[400010];
int tot, ans[400010], cnt[400010];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &h[i]);
    ls[i] = h[i];
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a[i], &b[i]);
    ls[i + n] = b[i];
  }
  sort(ls + 1, ls + n + m + 1);
  End = unique(ls + 1, ls + n + m + 1) - ls;
  for (int i = 1; i <= n; i++) h[i] = lower_bound(ls + 1, ls + End, h[i]) - ls;
  for (int i = 1; i <= m; i++) b[i] = lower_bound(ls + 1, ls + End, b[i]) - ls;
  for (int i = 1; i <= m; i++) {
    p[a[i]].push_back(make_pair(b[i], i));
  }
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    pre[i] = T1.query(h[i] - 1) + 1;
    tot = max(tot, pre[i]);
    T1.modify(h[i], pre[i]);
  }
  for (int i = n; i >= 1; i--) {
    suf[i] = T2.query(h[i] + 1) + 1;
    T2.modify(h[i], suf[i]);
  }
  T1.clear();
  for (int i = 1; i <= n; i++) {
    for (auto &x : p[i]) f0[x.second] = T1.query(x.first - 1);
    T1.modify(h[i], pre[i]);
  }
  T2.clear();
  for (int i = n; i >= 1; i--) {
    for (auto &x : p[i]) g0[x.second] = T2.query(x.first + 1);
    T2.modify(h[i], suf[i]);
  }
  for (int i = 1; i <= n; i++) cnt[pre[i]] += (pre[i] + suf[i] - 1 == tot);
  for (int i = 1; i <= n; i++) {
    for (auto &x : p[i]) {
      if (f0[x.second] + g0[x.second] + 1 > tot)
        ans[x.second] = tot + 1;
      else if (f0[x.second] + g0[x.second] + 1 == tot)
        ans[x.second] = tot;
      else if (cnt[pre[i]] == 1 && pre[i] + suf[i] - 1 == tot)
        ans[x.second] = tot - 1;
      else
        ans[x.second] = tot;
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
