#include <bits/stdc++.h>
using namespace std;
struct Node {
  Node *lch, *rch;
  int seg;
  Node() {
    lch = rch = nullptr;
    seg = 0;
  }
  inline void up() { seg = max(lch->seg, rch->seg); }
} space[1800000], *ptr = space, *root;
void init(int l, int r, Node*& node) {
  node = new (ptr++) Node();
  if (l != r) {
    int mid = (l + r) >> 1;
    init(l, mid, node->lch);
    init(mid + 1, r, node->rch);
  }
}
void modify(int l, int r, int pos, int v, Node* node) {
  if (l == r) {
    node->seg = max(node->seg, v);
  } else {
    int mid = (l + r) >> 1;
    if (pos <= mid)
      modify(l, mid, pos, v, node->lch);
    else
      modify(mid + 1, r, pos, v, node->rch);
    node->up();
  }
}
int query(int l, int r, int ql, int qr, Node* node) {
  if (l == ql && r == qr) return node->seg;
  int mid = (l + r) >> 1;
  if (qr <= mid)
    return query(l, mid, ql, qr, node->lch);
  else if (ql > mid)
    return query(mid + 1, r, ql, qr, node->rch);
  return max(query(l, mid, ql, mid, node->lch),
             query(mid + 1, r, mid + 1, qr, node->rch));
}
int xs[800010], sz;
int h[400010], len[400010], len2[400010], ch_len[400010], cnt[400010];
vector<pair<int, int> > ch[400010];
pair<int, int> q[400010];
int main() {
  int n, m, a, b;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", h + i);
    xs[sz++] = h[i];
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a, &b);
    xs[sz++] = b;
    q[i] = pair<int, int>(a, b);
  }
  xs[sz++] = 0;
  xs[sz++] = 1000000001;
  sort(xs, xs + sz);
  sz = unique(xs, xs + sz) - xs;
  ptr = space;
  init(0, sz - 1, root);
  for (int i = 1; i <= n; i++) h[i] = lower_bound(xs, xs + sz, h[i]) - xs;
  for (int i = 1; i <= m; i++) {
    q[i].second = lower_bound(xs, xs + sz, q[i].second) - xs;
    ch[q[i].first].push_back(pair<int, int>(q[i].second, i));
  }
  int maxL = 0;
  for (int i = 1; i <= n; i++) {
    int res = query(0, sz - 1, 0, h[i] - 1, root);
    len[i] = res + 1;
    for (pair<int, int>& p : ch[i])
      ch_len[p.second] = query(0, sz - 1, 0, p.first - 1, root) + 1;
    modify(0, sz - 1, h[i], len[i], root);
    if (len[i] > maxL) maxL = len[i];
  }
  ptr = space;
  init(0, sz - 1, root);
  modify(0, sz - 1, sz - 1, 0, root);
  for (int i = n; i >= 1; i--) {
    int res = query(0, sz - 1, h[i] + 1, sz - 1, root);
    if (len[i] + res == maxL) cnt[len[i]]++;
    len2[i] = res;
    for (pair<int, int>& p : ch[i])
      ch_len[p.second] += query(0, sz - 1, p.first + 1, sz - 1, root);
    modify(0, sz - 1, h[i], res + 1, root);
  }
  for (int i = 1; i <= m; i++) {
    if (len[q[i].first] + len2[q[i].first] == maxL && cnt[len[q[i].first]] == 1)
      printf("%d\n", max(maxL - 1, ch_len[i]));
    else
      printf("%d\n", max(maxL, ch_len[i]));
  }
  return 0;
}
