#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int MOD = 1e9 + 7;
const int N = 5e5 + 10;
int n, m, a[N], ans[N];
int lis[N], lds[N], always[N];
int s[N];
vector<pair<int, int> > v[N];
vector<int> v2[N];
void prepare() {
  scanf("%d%d", &n, &m);
  for (auto i = (1); i <= (n); i++) scanf("%d", a + i);
  for (auto i = (1); i <= (m); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(pair<int, int>(y, i));
  }
  int top = 0;
  for (auto i = (1); i <= (n); i++) {
    for (auto j : v[i])
      ans[j.second] += lower_bound(s + 1, s + top + 1, j.first) - s;
    int idx = lower_bound(s + 1, s + top + 1, a[i]) - s;
    lis[i] = idx;
    s[idx] = a[i];
    if (idx > top) top++;
  }
  top = 0;
  for (auto i = (n); i >= (1); i--) {
    for (auto j : v[i])
      ans[j.second] +=
          lower_bound(s + 1, s + top + 1, j.first, greater<int>()) - s;
    int idx = lower_bound(s + 1, s + top + 1, a[i], greater<int>()) - s;
    lds[i] = idx;
    s[idx] = a[i];
    if (idx > top) top++;
  }
}
void solve() {
  int alis = 0;
  for (auto i = (1); i <= (n); i++) alis = max(alis, lis[i] + lds[i]);
  for (auto i = (1); i <= (n); i++) {
    always[i] = (lis[i] + lds[i]) == alis;
    if (always[i]) v2[lis[i]].push_back(i);
  }
  for (auto i = (1); i <= (n); i++)
    if (v2[i].size() > 1)
      for (auto j : v2[i]) always[j] = 0;
  for (auto i = (1); i <= (n); i++)
    for (auto j : v[i]) ans[j.second] = max(ans[j.second], alis - always[i]);
  for (auto i = (1); i <= (m); i++) printf("%d\n", ans[i] - 1);
}
int main() {
  prepare();
  solve();
}
