#include <bits/stdc++.h>
using namespace std;
void bug() { cout << " " << endl; }
template <class T>
void bug(T a) {
  cout << a << "  ";
}
template <class T>
void bug(T* a, int n) {
  for (int i = 0; i < (n); i++) bug(a[i]);
}
struct node {
  node *l, *r;
  int maxv;
};
node a[2000001];
int N;
node* build(int l, int r) {
  node* root = &a[++N];
  root->maxv = -1;
  if (l == r) return root;
  root->l = build(l, (l + r) / 2);
  root->r = build((l + r) / 2 + 1, r);
  return root;
}
int ask(int l, int r, node* root, int B, int E) {
  if (l > r) return -1;
  if (r < B || E < l) return -1;
  if (l <= B && E <= r) return root->maxv;
  return max(ask(l, r, root->l, B, (B + E) / 2),
             ask(l, r, root->r, (B + E) / 2 + 1, E));
}
node* insert(int x, int h, node* root, int B, int E) {
  if (x < B || E < x) return root;
  if (B == E) {
    node* ret = root;
    ret->maxv = max(h, root->maxv);
    return ret;
  }
  node* ret = root;
  ret->maxv = max(h, root->maxv);
  ret->l = root->l;
  ret->r = root->r;
  int mid = (B + E) / 2;
  if (x <= mid)
    insert(x, h, root->l, B, mid);
  else
    insert(x, h, root->r, mid + 1, E);
  return ret;
}
const int maxn = 444445;
int n, m, h[maxn];
vector<int> ls;
node *r[maxn], *rr[maxn], *root;
int OPT;
vector<int> lis[maxn];
bool must[maxn];
int rdp[maxn], dp[maxn], cnt[maxn];
pair<int, int> q[maxn], ans[maxn];
vector<int> uq[maxn], dq[maxn];
int main() {
  ios::sync_with_stdio(false);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (n); i++) scanf("%d", h + i);
  for (int i = 0; i < (n); i++) ls.push_back(h[i]);
  sort(ls.begin(), ls.end());
  ls.erase(unique(ls.begin(), ls.end()), ls.end());
  for (int i = 0; i < (m); i++) {
    scanf("%d%d", &q[i].first, &q[i].second);
    int index = q[i].first - 1;
    dq[index].push_back(i);
    uq[index].push_back(i);
  }
  for (int i = 0; i < (n); i++)
    h[i] = lower_bound(ls.begin(), ls.end(), h[i]) - ls.begin();
  root = build(0, n - 1);
  node* last = root;
  for (int i = 0; i < (n); i++) {
    for (int j : dq[i]) {
      int x = lower_bound(ls.begin(), ls.end(), q[j].second) - ls.begin() - 1;
      ans[j].first = max(ask(0, x, last, 0, n - 1), 0);
    }
    int val = max(ask(0, h[i] - 1, last, 0, n - 1), 0);
    OPT = max(OPT, val + 1);
    dp[i] = val + 1;
    lis[val + 1].push_back(i);
    last = r[i] = insert(h[i], val + 1, last, 0, n - 1);
  }
  N = 0;
  root = build(0, n - 1);
  last = root;
  for (int i = n - 1; i >= 0; --i) {
    for (int j : uq[i]) {
      int y = upper_bound(ls.begin(), ls.end(), q[j].second) - ls.begin();
      ans[j].second = max(ask(y, n - 1, last, 0, n - 1), 0);
    }
    int val = max(0, ask(h[i] + 1, n - 1, last, 0, n - 1));
    rdp[i] = val + 1;
    last = rr[i] = insert(h[i], val + 1, last, 0, n - 1);
  }
  for (int i = 0; i < (n); i++)
    if (dp[i] + rdp[i] == OPT + 1) {
      cnt[dp[i]]++;
    }
  for (int i = 0; i < (n); i++)
    if (dp[i] + rdp[i] == OPT + 1 && cnt[dp[i]] == 1) must[i] = true;
  for (int i = 0; i < (m); i++) {
    int index = q[i].first - 1;
    int x = ans[i].first;
    int y = ans[i].second;
    int ans = 1 + x + y;
    if (!must[index])
      ans = max(ans, OPT);
    else
      ans = max(ans, OPT - 1);
    cout << ans << endl;
  }
  return 0;
}
