#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int h[MAXN], fen[MAXN], pre[MAXN], suf[MAXN], cnt[MAXN];
struct query {
  int id, a, b, pre, suf;
} q[MAXN];
bool operator<(query x, query y) { return x.a < y.a; }
bool compare(query x, query y) { return x.id < y.id; }
void upd(int idx, int val) {
  if (idx <= 0) return;
  for (; idx < MAXN; idx += idx & -idx) fen[idx] = max(fen[idx], val);
}
int get(int idx) {
  if (idx <= 0) return 0;
  int ret = 0;
  for (; idx; idx -= idx & -idx) ret = max(ret, fen[idx]);
  return ret;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> h[i];
  for (int i = 0; i < m; ++i) {
    cin >> q[i].a >> q[i].b;
    q[i].a--;
    q[i].id = i;
  }
  vector<int> com;
  for (int i = 0; i < n; ++i) com.push_back(h[i]);
  for (int i = 0; i < m; ++i) com.push_back(q[i].b);
  sort(com.begin(), com.end());
  com.resize(unique(com.begin(), com.end()) - com.begin());
  for (int i = 0; i < n; ++i)
    h[i] = lower_bound(com.begin(), com.end(), h[i]) - com.begin() + 1;
  for (int i = 0; i < m; ++i)
    q[i].b = lower_bound(com.begin(), com.end(), q[i].b) - com.begin() + 1;
  int LIS = 0;
  for (int i = 0; i < n; ++i) {
    pre[i] = get(h[i] - 1) + 1;
    LIS = max(LIS, pre[i]);
    upd(h[i], pre[i]);
  }
  memset(fen, 0, sizeof fen);
  for (int i = n - 1; i >= 0; --i) {
    suf[i] = get(MAXN - h[i] - 1) + 1;
    upd(MAXN - h[i], suf[i]);
    if (pre[i] + suf[i] - 1 == LIS) cnt[pre[i]]++;
  }
  vector<int> spec;
  for (int i = 0; i < n; ++i)
    if (pre[i] + suf[i] - 1 == LIS && cnt[pre[i]] == 1) spec.push_back(i);
  sort(q, q + m);
  memset(fen, 0, sizeof fen);
  int ptr = 0;
  for (int i = 0; i < n; ++i) {
    while (ptr < m && q[ptr].a == i) {
      q[ptr].pre = get(q[ptr].b - 1) + 1;
      ptr++;
    }
    upd(h[i], get(h[i] - 1) + 1);
  }
  memset(fen, 0, sizeof fen);
  ptr = m - 1;
  for (int i = n - 1; i >= 0; --i) {
    while (ptr >= 0 && q[ptr].a == i) {
      q[ptr].suf = get(MAXN - q[ptr].b - 1) + 1;
      ptr--;
    }
    upd(MAXN - h[i], get(MAXN - h[i] - 1) + 1);
  }
  sort(q, q + m, compare);
  for (int i = 0; i < m; ++i) {
    int ans = LIS - 1;
    if (!binary_search(spec.begin(), spec.end(), q[i].a)) ans = LIS;
    cout << max(ans, q[i].pre + q[i].suf - 1) << "\n";
  }
}
