#include <bits/stdc++.h>
using namespace std;
int n, m, a[400005], mark1[400005], mark2[400005], idx1[400005], len,
    idx2[400005], p1[400005], p2[400005], res1[400005], res2[400005];
vector<int> b(400005), c(400005);
vector<int> s1, s2;
typedef struct qu {
  int i;
  int q;
  int v;
  int a;
} query;
typedef struct chan {
  int in;
  int val;
} ch;
ch y[400005];
bool f1(query l, query r) { return l.i < r.i; }
bool f2(int a, int b) { return a > b; }
bool f3(query l, query r) { return l.q < r.q; }
int max(int a, int b) { return (a > b) ? a : b; }
query k[400005];
void build_reverse() {
  for (int i = 0; i <= n; i++) b[i] = -1000000007, idx1[i] = -1;
  b[0] = 1000000007;
  for (int i = n - 1; i >= 0; i--) {
    auto it = lower_bound(b.begin(), b.begin() + n + 1, a[i], f2);
    y[i].in = res1[i] = it - b.begin();
    y[i].val = b[y[i].in];
    b[y[i].in] = a[i];
    p1[i] = idx1[y[i].in - 1];
    idx1[y[i].in] = i;
  }
  len = 0;
  for (int i = 1; i <= n; i++) {
    if (b[i] != -1000000007) len = i;
  }
}
void build_forward() {
  for (int i = 0; i <= n; i++) c[i] = 1000000007, idx2[i] = -1;
  c[0] = -1000000007;
  for (int i = 0; i < n; i++) {
    auto it = lower_bound(c.begin(), c.begin() + n + 1, a[i]);
    res2[i] = it - c.begin();
    c[res2[i]] = a[i];
    p2[i] = idx2[res2[i] - 1];
    idx2[res2[i]] = i;
  }
}
void solve() {
  int plt = 0, prt = 0;
  for (int i = 0; i <= n; i++) c[i] = 1000000007;
  c[0] = -1000000007;
  int j = 0;
  for (int i = 0; i < n; i++) {
    prt = y[i].in;
    b[prt] = y[i].val;
    while (k[j].i == i) {
      if (mark1[i] && mark2[i])
        k[j].a = len - 1;
      else
        k[j].a = len;
      int x = k[j].v;
      auto it = lower_bound(c.begin(), c.begin() + n + 1, x);
      int inc = (it == c.begin()) ? 0 : (it - c.begin() - 1) + 1;
      it = lower_bound(b.begin(), b.begin() + n + 1, x, f2);
      inc += (it == b.begin()) ? 0 : (it - b.begin() - 1);
      k[j].a = max(k[j].a, inc);
      j++;
    }
    auto it = lower_bound(c.begin(), c.begin() + n + 1, a[i]);
    plt = it - c.begin();
    c[plt] = a[i];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    cin >> k[i].i >> k[i].v;
    k[i].i--;
    k[i].q = i;
    k[i].a = 0;
  }
  sort(k, k + m, f1);
  build_reverse();
  build_forward();
  int t, mx = -1;
  for (int i = 0; i < n; i++) {
    if (mx <= res2[i]) {
      mx = res2[i];
      t = i;
    }
  }
  while (p2[t] != -1) {
    mark2[t] = 1;
    t = p2[t];
  }
  mark2[t] = 1;
  for (int i = 0; i < s2.size(); i++)
    cout << s2[i] << " "
         << "\n";
  mx = -1;
  for (int i = n - 1; i >= 0; i--) {
    if (mx <= res1[i]) {
      mx = res1[i];
      t = i;
    }
  }
  while (p1[t] != -1) {
    mark1[t] = 1;
    t = p1[t];
  }
  mark1[t] = 1;
  solve();
  sort(k, k + m, f3);
  for (int i = 0; i < m; i++) cout << k[i].a << "\n";
  return 0;
}
