#include <bits/stdc++.h>
using namespace std;
int bit[800800];
void bitu(int idx, int val) {
  ;
  idx++;
  while (idx < 800800) {
    bit[idx] += val;
    idx += idx & -idx;
  }
}
int bitq(int idx) {
  ;
  idx++;
  int ret = 0;
  while (idx) {
    ret += bit[idx];
    idx -= idx & -idx;
  };
  return ret;
}
int T[4 * 800800];
void update(int init, int fim, int p, int pos, int val) {
  if (init > pos || fim < pos) return;
  if (init == fim) {
    T[p] = val;
    return;
  }
  int mid = (init + fim) / 2;
  update(init, mid, 2 * p, pos, val);
  update(mid + 1, fim, 2 * p + 1, pos, val);
  T[p] = max(T[2 * p], T[2 * p + 1]);
}
int query(int init, int fim, int p, int l, int r) {
  if (init > r || fim < l) return 0;
  if (init >= l && fim <= r) return T[p];
  int mid = (init + fim) / 2;
  return max(query(init, mid, 2 * p, l, r),
             query(mid + 1, fim, 2 * p + 1, l, r));
}
int v[800800];
int qual[800800];
int to[800800];
int dpl[800800];
int dpr[800800];
vector<pair<int, int> > ask[800800];
vector<pair<int, int> > answer[800800];
int resp[800800];
set<int> S[800800];
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  int N = n + q + 3;
  vector<pair<int, int> > vec;
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    vec.push_back(pair<int, int>(a, i));
  }
  for (int i = 0; i < q; i++) {
    int id, h;
    scanf("%d%d", &id, &h), id--;
    qual[i] = id;
    vec.push_back(pair<int, int>(h, n + i));
  }
  sort(vec.begin(), vec.end());
  int cur = 0;
  for (int i = 0; i < vec.size(); i++) {
    if (i && vec[i].first != vec[i - 1].first) cur++;
    if (vec[i].second < n)
      v[vec[i].second] = cur;
    else
      to[vec[i].second - n] = cur;
  }
  for (int i = 0; i < q; i++) ask[qual[i]].push_back(pair<int, int>(to[i], i));
  ;
  for (int i = 0; i < n; i++)
    ;
  ;
  for (int i = n - 1; i >= 0; i--) {
    dpr[i] = 1 + query(0, N - 1, 1, v[i] + 1, N - 1);
    ;
    for (int j = 0; j < ask[i].size(); j++) {
      int u = 1 + query(0, N - 1, 1, ask[i][j].first + 1, N - 1);
      answer[i].push_back(pair<int, int>(-1, u));
    }
    update(0, N - 1, 1, v[i], dpr[i]);
    ;
  }
  for (int i = 0; i < N; i++) update(0, N - 1, 1, i, 0);
  for (int i = 0; i < n; i++) {
    dpl[i] = 1 + query(0, N - 1, 1, 0, v[i] - 1);
    for (int j = 0; j < ask[i].size(); j++) {
      int u = 1 + query(0, N - 1, 1, 0, ask[i][j].first - 1);
      answer[i][j].first = u;
    }
    update(0, N - 1, 1, v[i], dpl[i]);
  }
  int lis = 0;
  for (int i = 0; i < n; i++) lis = max(lis, dpr[i]);
  int first = n - 1;
  for (int i = n - 1; i >= 0; i--)
    if (dpl[i] == lis) first = i;
  if (first != n - 1) {
    bitu(first + 1, 1);
    bitu(n, -1);
    ;
  }
  first = 0;
  for (int i = 0; i < n; i++)
    if (dpr[i] == lis) first = i;
  bitu(0, 1);
  bitu(first, -1);
  ;
  ;
  for (int i = 0; i < n; i++)
    ;
  vector<pair<int, int> > vv;
  for (int i = 0; i < n; i++) vv.push_back(pair<int, int>(v[i], i));
  sort(vv.begin(), vv.end());
  reverse(vv.begin(), vv.end());
  int ptr = 0;
  for (int i = 0; i < n; i++) {
    int p0 = ptr;
    while (ptr < n && vv[ptr].first == vv[p0].first) ptr++;
    for (int j = p0; j < ptr; j++) {
      int pos = vv[j].second;
      int dp_pos = dpl[pos];
      int need = lis - dp_pos;
      if (S[need].size() == 0) continue;
      int big = *(--S[need].end());
      if (big - 1 < pos + 1) continue;
      bitu(pos + 1, 1);
      bitu(big, -1);
      ;
    }
    for (int j = p0; j < ptr; j++) S[dpr[vv[j].second]].insert(vv[j].second);
  }
  for (int i = 0; i < q; i++) {
    int ans = lis - 1;
    if (bitq(qual[i])) {
      ans = lis;
      ;
    }
    resp[i] = ans;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < ask[i].size(); j++) {
      resp[ask[i][j].second] = max(
          resp[ask[i][j].second], answer[i][j].first + answer[i][j].second - 1);
      ;
    }
  for (int i = 0; i < q; i++) printf("%d\n", resp[i]);
}
