#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 400100;
int n, m;
int lis;
int a[N], b[N];
struct Que {
  int a, b;
} que[N];
int hn;
int h[N];
void init_Hash() {
  for (int i = 1; i <= n; i++) h[i] = a[i];
  sort(h + 1, h + n + 1);
  hn = unique(h + 1, h + n + 1) - h - 1;
}
int Hash(int x, int t) {
  int res = lower_bound(h + 1, h + hn + 1, x) - h;
  if (t == 0)
    return res;
  else if (t == 1)
    return res - 1;
  else {
    if (h[res] == x)
      return res + 1;
    else
      return res;
  }
}
int lis_l[N], lis_r[N], g[N];
void LIS() {
  for (int i = 1; i <= n; i++) g[i] = inf;
  for (int i = 1; i <= n; i++) {
    int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
    lis_l[i] = k;
    lis = max(k, lis);
    g[k] = a[i];
  }
  for (int i = 1; i <= n; i++) b[i] = inf - a[i];
  for (int i = 1; i <= n; i++) g[i] = inf;
  for (int i = n; i >= 1; i--) {
    int k = lower_bound(g + 1, g + n + 1, b[i]) - g;
    lis_r[i] = k;
    g[k] = b[i];
  }
}
int pos[N], num[N];
void pre() {
  for (int i = 1; i <= n; i++) {
    if (lis_l[i] + lis_r[i] == lis + 1) {
      pos[i] = lis_l[i];
      num[pos[i]]++;
    }
  }
}
int tot;
int rt[N], ls[N * 25], rs[N * 25], mx[N * 25];
void init() {
  tot = 0;
  memset(rt, 0, sizeof rt);
  memset(ls, 0, sizeof ls);
  memset(rs, 0, sizeof rs);
  memset(mx, 0, sizeof mx);
}
void build(int l, int r, int& rt) {
  rt = tot++;
  if (l == r) return;
  int m = (l + r) >> 1;
  build(l, m, ls[rt]);
  build(m + 1, r, rs[rt]);
}
void update(int pos, int v, int l, int r, int last, int& rt) {
  rt = tot++;
  ls[rt] = ls[last];
  rs[rt] = rs[last];
  mx[rt] = max(mx[last], v);
  if (l == r) return;
  int m = (l + r) >> 1;
  if (pos <= m)
    update(pos, v, l, m, ls[last], ls[rt]);
  else
    update(pos, v, m + 1, r, rs[last], rs[rt]);
}
int query(int ll, int rr, int l, int r, int rt) {
  if (ll <= l && r <= rr) return mx[rt];
  int m = (l + r) >> 1;
  if (rr <= m)
    return query(ll, rr, l, m, ls[rt]);
  else if (ll > m)
    return query(ll, rr, m + 1, r, rs[rt]);
  else
    return max(query(ll, rr, l, m, ls[rt]), query(ll, rr, m + 1, r, rs[rt]));
}
int dp1[N], dp2[N];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> que[i].a >> que[i].b;
  init_Hash();
  LIS();
  pre();
  init();
  build(1, hn, rt[0]);
  for (int i = 1; i <= n; i++) {
    int pos = Hash(a[i], 0);
    update(pos, lis_l[i], 1, hn, rt[i - 1], rt[i]);
  }
  for (int i = 0; i < m; i++) {
    int pos = Hash(que[i].b, 1);
    if (pos) dp1[i] = query(1, pos, 1, hn, rt[que[i].a - 1]);
  }
  init();
  build(1, hn, rt[n + 1]);
  for (int i = n; i >= 1; i--) {
    int pos = Hash(a[i], 0);
    update(pos, lis_r[i], 1, hn, rt[i + 1], rt[i]);
  }
  for (int i = 0; i < m; i++) {
    int pos = Hash(que[i].b, 2);
    if (pos != hn + 1) dp2[i] = query(pos, hn, 1, hn, rt[que[i].a + 1]);
  }
  for (int i = 0; i < m; i++) {
    int ans = dp1[i] + dp2[i] + 1;
    if (num[pos[que[i].a]] == 1)
      ans = max(ans, lis - 1);
    else
      ans = max(ans, lis);
    cout << ans << endl;
  }
  return 0;
}
