#include <bits/stdc++.h>
using namespace std;
int d1[401010], d2[401010], a[401010], st[401010], sum[401010], D2[401010],
    b[401010], c[401010], out[401010];
pair<int, int> s1[401010], s2[401010];
int main() {
  int n, m, lis = 0, inf = 1145141919;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < n + 10; i++) s1[i] = s2[i] = make_pair(-1, -1);
  for (int i = 0; i < n + 10; i++) d1[i] = inf;
  d1[0] = 0;
  for (int i = 0; i < n; i++) {
    int t = lower_bound(d1, d1 + n + 5, a[i]) - d1;
    if (a[i] < d1[t]) s1[i] = make_pair(t, a[i]), d1[t] = a[i];
  }
  for (int i = 0; i < n + 2; i++) {
    if (d1[i] < inf) lis = i;
  }
  memset(d2, 0, sizeof(d2));
  d2[0] = -inf;
  for (int i = n - 1; i >= 0; i--) {
    int t = lower_bound(d2, d2 + n + 5, -a[i]) - d2;
    if (-a[i] < d2[t]) s2[i] = make_pair(t, d2[t]), d2[t] = -a[i];
  }
  for (int i = 0; i < n + 10; i++) D2[i] = d2[i];
  memset(sum, 0, sizeof(sum));
  memset(st, -1, sizeof(st));
  for (int i = 0; i < n + 10; i++) d1[i] = inf;
  d1[0] = 0;
  for (int i = 0; i < n; i++) {
    if (s2[i].first >= 0) d2[s2[i].first] = s2[i].second;
    int x = lower_bound(d1, d1 + n + 5, a[i]) - d1,
        y = lower_bound(d2, d2 + n + 5, -a[i]) - d2;
    if (x + y - 1 == lis) st[i] = x, sum[x]++;
    if (s1[i].first >= 0) d1[s1[i].first] = s1[i].second;
  }
  vector<pair<int, int> > p;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &b[i], &c[i]);
    b[i]--;
    p.push_back(make_pair(b[i], i));
  }
  sort(p.begin(), p.end());
  for (int i = 0; i < n + 10; i++) d1[i] = inf;
  d1[0] = 0;
  for (int i = 0; i < n + 10; i++) d2[i] = D2[i];
  if (s2[0].first >= 0) d2[s2[0].first] = s2[0].second;
  int now = 0;
  for (int i = 0; i < m; i++) {
    int s = p[i].first, t = p[i].second;
    while (s > now) {
      if (s1[now].first >= 0) d1[s1[now].first] = s1[now].second;
      now++;
      if (s2[now].first >= 0) d2[s2[now].first] = s2[now].second;
    }
    out[t] = lis - 1;
    if (st[s] < 0 || sum[st[s]] > 1) out[t] = lis;
    int x = lower_bound(d1, d1 + n + 5, c[t]) - d1,
        y = lower_bound(d2, d2 + n + 5, -c[t]) - d2;
    out[t] = max(out[t], x + y - 1);
  }
  for (int i = 0; i < m; i++) printf("%d\n", out[i]);
}
