#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(int a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(int a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  write(a);
  puts("");
}
const int N = 400005;
int n, m, arr[N], er[N], len, oo = 1000000005, ans1[N], ans2[N], instead[N],
                              tong[N], f[N], ans3[N];
struct data {
  int a, b, id;
} q[N];
inline bool cmp(data a, data b) { return a.a < b.a; }
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    arr[i] = read();
  }
  for (int i = 1; i <= m; i++) {
    q[i].a = read();
    q[i].b = read();
    q[i].id = i;
  }
  sort(&q[1], &q[m + 1], cmp);
  int j = 1;
  er[1] = oo;
  for (int i = 1; i <= n; i++) {
    for (; j <= m && q[j].a == i; j++) {
      ans1[q[j].id] = lower_bound(&er[1], &er[len + 2], q[j].b) - er - 1;
    }
    int t = lower_bound(&er[1], &er[len + 2], arr[i]) - er;
    er[t] = arr[i];
    f[i] = t;
    if (t > len) {
      len++;
      er[len + 1] = oo;
    }
  }
  int anan = len;
  j = m;
  len = 0;
  for (int i = n; i; i--) {
    for (; j && q[j].a == i; j--)
      ans2[q[j].id] = lower_bound(&er[1], &er[len + 2], -q[j].b) - er - 1;
    int t = lower_bound(&er[1], &er[len + 2], -arr[i]) - er;
    er[t] = -arr[i];
    if (f[i] + t - 1 == anan) {
      if (tong[f[i]]) {
        instead[tong[f[i]]] = instead[i] = 0;
      } else {
        tong[f[i]] = i;
        instead[i] = 1;
      }
    }
    if (t > len) {
      len++;
      er[len + 1] = oo;
    }
  }
  for (int i = 1; i <= m; i++)
    if (instead[q[i].a])
      ans3[q[i].id] = len - 1;
    else
      ans3[q[i].id] = len;
  for (int i = 1; i <= m; i++) writeln(max(ans1[i] + ans2[i] + 1, ans3[i]));
}
