#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int N = 5e5 + 100, OO = 1e6, T = (1 << 20) + 10, M = 998244353, P = 6151,
          SQ = 280, lg = 64;
int a[N], b[N];
vector<int> v, v1, t, t1;
vector<pair<int, int> > is[N];
int dp[N], dp1[N], ant[N], ans[N], n1[N], n2[N];
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    is[x - 1].push_back({y, i});
  }
  for (int i = 0; i < n; i++) {
    for (auto u : is[i]) {
      int l = 0, r = (int)v.size();
      int nw = u.first;
      while (l < r) {
        int mid = (l + r) / 2;
        if (v[mid] >= nw)
          r = mid;
        else
          l = mid + 1;
      }
      n1[u.second] = l + 1;
    }
    int l = 0, r = (int)v.size();
    while (l < r) {
      int mid = (l + r) / 2;
      if (v[mid] >= a[i])
        r = mid;
      else
        l = mid + 1;
    }
    if (l == (int)v.size())
      v.push_back(a[i]);
    else
      v[l] = a[i];
    dp[i] = l + 1;
    b[i] = -1 * a[i];
  }
  int lis = (int)v.size();
  for (int i = n - 1; i >= 0; i--) {
    for (auto u : is[i]) {
      int l = 0, r = (int)v1.size();
      int nw = u.first * -1;
      while (l < r) {
        int mid = (l + r) / 2;
        if (v1[mid] >= nw)
          r = mid;
        else
          l = mid + 1;
      }
      n2[u.second] = l;
    }
    int l = 0, r = (int)v1.size();
    while (l < r) {
      int mid = (l + r) / 2;
      if (v1[mid] >= b[i])
        r = mid;
      else
        l = mid + 1;
    }
    if (l + dp[i] == (int)v.size())
      ans[i] = 3, t.push_back(a[i]), t1.push_back(i);
    else
      ans[i] = 1;
    if (l == (int)v1.size())
      v1.push_back(b[i]);
    else
      v1[l] = b[i];
  }
  v.clear();
  v1.clear();
  for (int i = t.size() - 1; i >= 0; i--) {
    int l = 0, r = (int)v.size();
    while (l < r) {
      int mid = (l + r) / 2;
      if (v[mid] >= t[i])
        r = mid;
      else
        l = mid + 1;
    }
    if (l == (int)v.size()) {
      v.push_back(t[i]);
      v1.push_back(t1[i]);
    } else {
      ans[v1[l]] = 2;
      ans[t1[i]] = 2;
      v[l] = t[i];
      v1[l] = t1[i];
    }
  }
  for (int i = 0; i < n; i++) {
    for (auto u : is[i]) {
      int lt = n1[u.second] + n2[u.second];
      if (lt >= lis) {
        ant[u.second] = lt;
        continue;
      }
      if (ans[i] == 1 || ans[i] == 2) {
        ant[u.second] = lis;
        continue;
      } else
        ant[u.second] = lis - 1;
    }
  }
  for (int i = 0; i < m; i++) cout << ant[i] << endl;
  return 0;
}
