#include <bits/stdc++.h>
using namespace std;
template <class T>
using vec = vector<T>;
template <typename Iter>
ostream &_IterOutput_(ostream &o, Iter b, Iter e, const string ss = "",
                      const string se = "") {
  o << ss;
  for (auto it = b; it != e; it++) o << (it == b ? "" : ", ") << *it;
  return o << se;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &o, pair<T1, T2> &pair) {
  return o << "(" << pair.first << ", " << pair.second << ")";
}
template <typename T>
ostream &operator<<(ostream &o, const vector<T> &vec) {
  return _IterOutput_(o, begin(vec), end(vec), "[", "]");
}
template <typename T>
ostream &operator<<(ostream &o, const set<T> &st) {
  return _IterOutput_(o, begin(st), end(st), "{", "}");
}
template <typename T, size_t N>
ostream &operator<<(ostream &o, const array<T, N> &arr) {
  return _IterOutput_(o, begin(arr), end(arr), "|", "|");
}
inline int lb(int a) { return a & (-a); }
const int MX = 812345;
struct BIT {
  int v[MX];
  int qry(int a) {
    a += 2;
    int res = 0;
    while (a) {
      res = max(res, v[a]);
      a -= lb(a);
    }
    return res;
  }
  void chg(int a, int vv) {
    a += 2;
    while (a < MX) {
      v[a] = max(v[a], vv);
      a += lb(a);
    }
  }
  void init() { memset((v), 0, sizeof(v)); }
} b1;
int N, Q;
vec<int> ip;
vec<pair<int, int> > qry;
vector<pair<int, int> > qq[MX];
vec<int> vs;
int lans[MX], rans[MX];
bool isinp[MX];
int dp[MX];
bool cvt[MX];
int anscnt[MX];
int a1[MX], a2[MX];
int32_t main() {
  do {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  } while (0);
  cin >> N >> Q;
  ip.resize(N);
  for (int(i) = 0; (i) < (N); (i)++) {
    cin >> ip[i];
    vs.push_back(ip[i]);
  }
  qry.resize(Q);
  for (int(i) = 0; (i) < (Q); (i)++) {
    int a, b;
    cin >> a >> b;
    a--;
    vs.push_back(b);
    qry[i] = {a, b};
  }
  sort(begin(vs), end(vs));
  vs.resize(unique(begin(vs), end(vs)) - vs.begin());
  for (auto &x : ip) x = lower_bound(begin(vs), end(vs), x) - vs.begin();
  for (int(i) = 0; (i) < (Q); (i)++) {
    auto p = qry[i];
    int t = lower_bound(begin(vs), end(vs), p.second) - vs.begin();
    p.second = t;
    qq[p.first].push_back({t, i});
  }
  int totans = 0;
  for (int i = 0; i < N; i++) {
    int v = ip[i];
    int bv = b1.qry(v - 1) + 1;
    dp[i] = bv;
    b1.chg(v, bv);
    totans = max(totans, bv);
  }
  static int tmp[MX];
  for (int i = N - 1; i >= 0; i--) {
    int v = ip[i];
    int d = dp[i];
    if (d == totans) {
      cvt[i] = 1;
      anscnt[d]++;
      tmp[d] = max(tmp[d], v);
    } else {
      int cc = tmp[d + 1];
      if (cc > v) {
        cvt[i] = 1;
        anscnt[d]++;
        tmp[d] = max(tmp[d], v);
      }
    }
  }
  for (int(i) = 0; (i) < (N); (i)++) {
    if (cvt[i] and anscnt[dp[i]] == 1) isinp[i] = 1;
    ;
  }
  b1.init();
  for (int(i) = 0; (i) < (N); (i)++) {
    for (auto q : qq[i]) {
      int qv = q.first, qid = q.second;
      a1[qid] = b1.qry(qv - 1);
    }
    b1.chg(ip[i], b1.qry(ip[i] - 1) + 1);
  }
  b1.init();
  int MAG = N + Q;
  for (int(i) = (N - 1); (i) != (-1); (i) += ((-1) > (N - 1) ? 1 : -1)) {
    for (auto q : qq[i]) {
      int qv = q.first, qid = q.second;
      a2[qid] = b1.qry(MAG - (qv + 1));
    }
    b1.chg(MAG - ip[i], b1.qry(MAG - (ip[i] + 1)) + 1);
  }
  for (int(i) = 0; (i) < (Q); (i)++) {
    auto q = qry[i];
    int j = q.first;
    int ans;
    if (isinp[j]) {
      ans = max(totans - 1, a1[i] + a2[i] + 1);
      ;
    } else {
      ans = max(totans, a1[i] + a2[i] + 1);
    }
    cout << ans << "\n";
  }
  return 0;
}
