#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[444444];
pair<pair<int, int>, int> q[444444];
int lft[444444], rgt[444444];
int ql[444444], qr[444444];
int tr[888888 << 2];
int ans[444444];
int red[888888], k;
map<pair<int, int>, int> old;
int findmax(int v, int l, int r, int st, int fn) {
  if (l == st && r == fn) return tr[v];
  int mid = (l + r + 1) / 2, ans = 0;
  if (st < mid) ans = max(ans, findmax(2 * v + 1, l, mid, st, min(mid, fn)));
  if (fn > mid) ans = max(ans, findmax(2 * v + 2, mid, r, max(st, mid), fn));
  return ans;
}
void upd(int v, int l, int r, int pos, int val) {
  if (l + 1 == r) {
    tr[v] = max(tr[v], val);
    return;
  }
  int mid = (l + r + 1) / 2;
  if (pos < mid)
    upd(2 * v + 1, l, mid, pos, val);
  else
    upd(2 * v + 2, mid, r, pos, val);
  tr[v] = max(tr[2 * v + 1], tr[2 * v + 2]);
}
inline void fill_it(int lft[444444], int ql[444444], bool ismore) {
  memset(tr, 0, sizeof(tr));
  int ptr = 0;
  for (int i = 0; i < n; ++i) {
    if (!ismore) {
      if (a[i]) lft[i] = findmax(0, 0, k, 0, a[i]);
    } else {
      if (a[i] != k - 1) lft[i] = findmax(0, 0, k, a[i] + 1, k);
    }
    while (1) {
      if (ptr == m) break;
      if (q[ptr].first.first < i) ++ptr;
      if (q[ptr].first.first >= i) break;
    }
    while (ptr < m && q[ptr].first.first == i) {
      if (!ismore) {
        if (q[ptr].first.second)
          ql[q[ptr].second] = findmax(0, 0, k, 0, q[ptr].first.second);
      } else {
        if (q[ptr].first.second != k - 1)
          ql[q[ptr].second] = findmax(0, 0, k, q[ptr].first.second + 1, k);
      }
      ++ptr;
    }
    upd(0, 0, k, a[i], lft[i] + 1);
  }
}
map<int, int> s;
int fq[444444];
int main() {
  k = 0;
  scanf("%d%d", &n, &m);
  memset(lft, 0, sizeof(lft));
  memset(rgt, 0, sizeof(rgt));
  memset(qr, 0, sizeof(qr));
  memset(ql, 0, sizeof(ql));
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    red[k++] = a[i];
  }
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &q[i].first.first, &q[i].first.second);
    red[k++] = q[i].first.second;
    --q[i].first.first;
    q[i].second = i;
  }
  sort(red, red + k);
  k = unique(red, red + k) - red;
  for (int i = 0; i < n; ++i) {
    a[i] = lower_bound(red, red + k, a[i]) - red;
  }
  for (int i = 0; i < m; ++i) {
    q[i].first.second = lower_bound(red, red + k, q[i].first.second) - red;
  }
  sort(q, q + m);
  fill_it(lft, ql, 0);
  reverse(q, q + m);
  reverse(a, a + n);
  for (int i = 0; i < m; ++i) q[i].first.first = n - 1 - q[i].first.first;
  fill_it(rgt, qr, 1);
  reverse(a, a + n);
  reverse(rgt, rgt + n);
  for (int i = 0; i < m; ++i) q[i].first.first = n - 1 - q[i].first.first;
  old.clear();
  int maxlen = 0;
  for (int i = 0; i < n; ++i) {
    old[make_pair(lft[i], rgt[i])]++;
    maxlen = max(maxlen, lft[i] + rgt[i] + 1);
  }
  for (int i = 0; i < m; ++i) {
    int pos = q[i].first.first;
    int len = qr[q[i].second] + ql[q[i].second] + 1;
    if (lft[pos] + rgt[pos] + 1 == maxlen) {
      if (old[make_pair(lft[pos], rgt[pos])] > 1) {
        len = max(len, lft[pos] + rgt[pos] + 1);
      } else {
        len = max(len, lft[pos] + rgt[pos]);
      }
    } else {
      len = max(len, maxlen);
    }
    ans[q[i].second] = len;
  }
  for (int i = 0; i < m; ++i) {
    printf("%d\n", ans[i]);
  }
}
