#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> fl, fr, f, ans;
struct Tree {
  int h, index;
  Tree *next;
  Tree(int hh, int ii, Tree *nn = NULL) : index(ii), h(hh), next(nn) {}
};
vector<Tree *> tree;
int binary_search(const vector<int> &arr, int target) {
  int l = 0, r = int(arr.size()) - 1;
  while (l < r) {
    int mid = (l + r) / 2;
    if (arr[mid + 1] < target)
      l = mid + 1;
    else
      r = mid;
  }
  return l;
}
vector<int> Lis(int rev) {
  vector<int> ret(n + 1), ma(1, -1000000001);
  if (rev == -1) {
    for (int i = 1; i <= n / 2; i++) swap(tree[i], tree[n - i + 1]);
  }
  for (int i = 1; i <= n; i++) {
    Tree *p = tree[i];
    while (p->next) {
      p = p->next;
      ans[p->index] += binary_search(ma, rev * p->h);
    }
    ret[i] = binary_search(ma, rev * tree[i]->h);
    if (ma.size() - 1 == ret[i]) {
      ma.push_back(rev * tree[i]->h);
    } else
      ma[ret[i] + 1] = rev * tree[i]->h;
  }
  if (rev == -1) {
    for (int i = 1; i <= n / 2; i++) swap(tree[i], tree[n - i + 1]);
    for (int i = 1; i <= n / 2; i++) swap(ret[i], ret[n - i + 1]);
  }
  return ret;
}
int ct[500000];
int main() {
  scanf("%d%d", &n, &m);
  fl.resize(n + 2);
  fr.resize(n + 2);
  tree.resize(n + 2);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    tree[i] = new Tree(x, 0);
  }
  ans.resize(m + 1);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    Tree *new_query = new Tree(b, i, tree[a]->next);
    tree[a]->next = new_query;
    ans[i] = 1;
  }
  fl = Lis(1);
  fr = Lis(-1);
  int lis = 1;
  for (int i = 1; i <= n; i++) {
    if (fl[i] + 1 > lis) lis = fl[i] + 1;
  }
  for (int i = 1; i <= n; i++) {
    if (fl[i] + fr[i] + 1 == lis) ct[fl[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    Tree *p = tree[i];
    int max_other = lis;
    if (fl[i] + fr[i] + 1 == lis && ct[fl[i]] == 1) max_other = lis - 1;
    while (p->next) {
      p = p->next;
      ans[p->index] = max(ans[p->index], max_other);
    }
  }
  for (int i = 1; i <= m; i++) {
    printf("%d\n", ans[i]);
  }
}
