#include <bits/stdc++.h>
using namespace std;
int a[400005], h[400005], dp[400005], dp2[400005], cnt[400005];
vector<int> v[400005];
int res[400005];
int aa[400005], bb[400005];
bool vis[400005];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) h[i] = 2e9;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int j = lower_bound(h + 1, h + 1 + n, a[i]) - h;
    dp[i] = j;
    h[j] = a[i];
    ans = max(ans, j);
  }
  int j = 1;
  for (int i = n; i >= 1; i--) {
    if (dp[i] == ans) {
      j = i;
      break;
    }
  }
  dp2[ans + 1] = 2e9;
  for (int i = j; i >= 1; i--) {
    if (a[i] < dp2[dp[i] + 1]) {
      dp2[dp[i]] = a[i];
      cnt[dp[i]]++;
      vis[i] = 1;
    }
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &aa[i], &bb[i]);
    v[aa[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) h[i] = 2e9;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < v[i].size(); j++) {
      int k = v[i][j];
      int val = bb[k];
      int l = lower_bound(h + 1, h + 1 + n, val) - h;
      res[k] += l;
    }
    int l = lower_bound(h + 1, h + 1 + n, a[i]) - h;
    h[l] = a[i];
  }
  for (int i = 1; i <= n; i++) h[i] = 2e9;
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < v[i].size(); j++) {
      int k = v[i][j];
      int val = -bb[k];
      int l = lower_bound(h + 1, h + 1 + n, val) - h;
      res[k] += l - 1;
    }
    a[i] = -a[i];
    int l = lower_bound(h + 1, h + 1 + n, a[i]) - h;
    h[l] = a[i];
  }
  for (int i = 1; i <= m; i++) {
    if (cnt[dp[aa[i]]] == 1 && vis[aa[i]])
      res[i] = max(res[i], ans - 1);
    else
      res[i] = max(res[i], ans);
    printf("%d\n", res[i]);
  }
}
