#include <bits/stdc++.h>
using namespace std;
const int INF = (-1u) / 2;
const long long int INF2 = (-1ull) / 2;
int a, b, i, d[400020], j, k, n, m, timer = 0, l[400020], r[400020], x, y;
int c[400020], cnt = 0, fl = 0, a2, a3 = -1000000, ans = 0, anl[400020],
               anr[400020];
vector<int> v, sm, sm2;
map<pair<int, int>, int> mpp;
int t[800010];
const int N = 800010;
vector<pair<int, pair<int, int> > > sl, sr;
unordered_map<int, int> mp, mp2;
pair<int, int> p[400020];
void update(int idx, int val) {
  while (idx <= N) {
    t[idx] = max(t[idx], val);
    idx += (idx & -idx);
  }
}
int take(int idx) {
  int res = 0;
  while (idx > 0) {
    res = max(res, t[idx]);
    idx -= (idx & -idx);
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  v.push_back(1000000000);
  for (i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    x = lower_bound(v.begin(), v.end(), c[i]) - v.begin();
    l[i] = x + 1;
    if (x == v.size()) {
      v.push_back(c[i]);
    } else {
      v[x] = c[i];
    }
    if (mp[c[i]] == 0) {
      mp[c[i]] = 1;
      sm.push_back(c[i]);
    }
  }
  k = v.size();
  if (v.size()) v.clear();
  v.push_back(1000000000);
  for (i = n; i >= 1; i--) {
    c[i] *= -1;
    x = lower_bound(v.begin(), v.end(), c[i]) - v.begin();
    r[i] = x + 1;
    if (x == v.size()) {
      v.push_back(c[i]);
    } else {
      v[x] = c[i];
    }
    if (mp2[c[i]] == 0) {
      sm2.push_back(c[i]);
      mp2[c[i]] = 1;
    }
    c[i] *= -1;
  }
  for (i = 1; i <= n; i++) {
    mpp[make_pair(l[i], r[i])]++;
  }
  for (i = 0; i < m; i++) {
    scanf("%d%d", &x, &y);
    p[i] = make_pair(x, y);
    if (mp[y - 1] == 0) {
      mp[y - 1] = 1;
      sm.push_back(y - 1);
    }
  }
  sort(sm.begin(), sm.end());
  for (i = 0; i < sm.size(); i++) {
    mp[sm[i]] = i + 1;
  }
  for (i = 0; i < m; i++) {
    sl.push_back(make_pair(p[i].first - 1, make_pair(mp[p[i].second - 1], i)));
    if (mp2[(p[i].second + 1) * -1] == 0) {
      sm2.push_back((p[i].second + 1) * -1);
      mp2[(p[i].second + 1) * -1] = 1;
    }
  }
  sort(sm2.begin(), sm2.end());
  for (i = 0; i < sm2.size(); i++) {
    mp2[sm2[i]] = i + 1;
  }
  for (i = 0; i < m; i++) {
    sr.push_back(
        make_pair(p[i].first + 1, make_pair(mp2[(p[i].second + 1) * -1], i)));
  }
  sort(sl.begin(), sl.end());
  x = 1;
  for (i = 0; i < sl.size(); i++) {
    a = sl[i].first;
    b = sl[i].second.first;
    while (x <= n && x <= a) {
      update(mp[c[x]], l[x]);
      x++;
    }
    anl[sl[i].second.second] = take(b);
  }
  for (i = 1; i <= N; i++) t[i] = 0;
  sort(sr.begin(), sr.end());
  x = n;
  for (i = sr.size() - 1; i >= 0; i--) {
    a = sr[i].first;
    b = sr[i].second.first;
    while (x > 0 && x >= a) {
      update(mp2[c[x] * -1], r[x]);
      x--;
    }
    anr[sr[i].second.second] = take(b);
  }
  for (i = 0; i < m; i++) {
    if (anl[i] + anr[i] + 1 >= k) {
      printf("%d\n", anl[i] + anr[i] + 1);
    } else if (l[p[i].first] + r[p[i].first] - 1 != k)
      printf("%d\n", k);
    else if (mpp[make_pair(l[p[i].first], r[p[i].first])] > 1)
      printf("%d\n", k);
    else
      printf("%d\n", k - 1);
  }
  return 0;
}
