#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using vb = vector<bool>;
using ii = pair<ll, ll>;
constexpr bool LOG = false;
void Log() {
  if (LOG) cerr << "\n";
}
template <class T, class... S>
void Log(T t, S... s) {
  if (LOG) cerr << t << "\t", Log(s...);
}
struct Q {
  ll x, h;
  ll before, after;
  ll i;
};
bool operator<(Q l, Q r) { return l.x < r.x; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, q;
  cin >> n >> q;
  vi a(n);
  for (auto &x : a) cin >> x;
  vector<Q> qs(q);
  ll _i = 0;
  for (auto &x : qs)
    cin >> x.x >> x.h, x.i = _i++, --x.x, x.before = x.after = 0;
  sort(begin(qs), end(qs));
  Log("forward dp");
  auto it = qs.begin();
  map<ll, ll> m;
  m[0] = 0;
  ll curmax = -1;
  vi before(n, 0), after(n, 0);
  for (auto i = decltype(n)(0); i < (n); ++i) {
    while (it != qs.end() && it->x == i) {
      it->before = prev(m.lower_bound(it->h))->second;
      ++it;
    }
    ll h = a[i];
    auto j = m.lower_bound(h);
    auto last = prev(j);
    ll val = last->second + 1;
    before[i] = val - 1;
    Log(i, h, "val", val);
    curmax = max(curmax, val);
    while (j != m.end() && j->second < val) j = m.erase(j);
    m.insert(j, {h, val});
  }
  Log("LIS:", curmax);
  Log("backward dp");
  map<ll, ll> m2;
  m2[1e10] = 0;
  auto bit = qs.rbegin();
  for (ll i = n - 1; i >= 0; --i) {
    while (bit != qs.rend() && bit->x == i) {
      bit->after = m2.lower_bound(bit->h + 1)->second;
      ++bit;
    }
    ll h = a[i];
    auto first = m2.lower_bound(h + 1);
    auto p = first;
    ll val = first->second + 1;
    after[i] = val - 1;
    while (p != m2.begin() && prev(p)->second <= val) p = m2.erase(prev(p));
    m2.insert(p, {h, val});
  }
  Log("finding needed elements");
  vi count(n, 0);
  Log("i", "before", "after");
  for (auto i = decltype(n)(0); i < (n); ++i) {
    Log(i, before[i], after[i]);
    if (before[i] + 1 + after[i] == curmax) ++count[before[i]];
  }
  Log("needed");
  vb needed(n, false);
  for (auto i = decltype(n)(0); i < (n); ++i)
    if (before[i] + 1 + after[i] == curmax && count[before[i]] == 1)
      needed[i] = true, Log("needed: ", i);
  sort(begin(qs), end(qs), [](Q l, Q r) { return l.i < r.i; });
  vi ans(q);
  for (auto i = decltype(q)(0); i < (q); ++i) {
    ll withq = qs[i].before + qs[i].after + 1;
    ll withoutq = curmax - needed[qs[i].x];
    Log(qs[i].x, "before, after", qs[i].before, qs[i].after, "withq withoutq",
        withq, withoutq);
    ans[qs[i].i] = max(withq, withoutq);
  }
  for (auto x : ans) cout << x << " ";
  cout << endl;
  return 0;
}
