#include <bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, m;
int a[N];
int b[N], q;
struct Chairman_Tree {
  int tot, root[N];
  struct Node {
    int Max, lc, rc;
  } tree[N * 20];
  int update(int i, int l, int r, int u, int val) {
    int now = ++tot;
    tree[now] = tree[i];
    tree[now].Max = max(tree[now].Max, val);
    if (l == r) return now;
    int mid = (l + r) / 2;
    if (u <= mid)
      tree[now].lc = update(tree[i].lc, l, mid, u, val);
    else
      tree[now].rc = update(tree[i].rc, mid + 1, r, u, val);
    return now;
  }
  int query(int i, int l, int r, int L, int R) {
    if (r < L || l > R) return 0;
    if (L <= l && r <= R) return tree[i].Max;
    int res = 0;
    int mid = (l + r) / 2;
    if (L <= mid) res = max(res, query(tree[i].lc, l, mid, L, R));
    if (R > mid) res = max(res, query(tree[i].rc, mid + 1, r, L, R));
    return res;
  }
} T[2];
int dp[2][N];
int S[N], cnt[N], LIS;
bool book[N];
void findLIS() {
  memset(S, 63, sizeof(S));
  for (int i = 1; i <= n; i++) {
    dp[0][i] = lower_bound(S, S + n, a[i]) - S + 1;
    S[dp[0][i] - 1] = a[i];
    LIS = max(LIS, dp[0][i]);
  }
  memset(S, 63, sizeof(S));
  for (int i = n; i >= 1; i--) {
    dp[1][i] = lower_bound(S, S + n, -a[i]) - S + 1;
    S[dp[1][i] - 1] = -a[i];
  }
  for (int i = 1; i <= n; i++)
    if (dp[0][i] + dp[1][i] == LIS + 1) book[i] = true, cnt[dp[0][i]]++;
  return;
}
void init() {
  for (int i = 1; i <= n; i++) b[++q] = a[i];
  sort(b + 1, b + q + 1);
  q = unique(b + 1, b + q + 1) - b - 1;
  for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
  findLIS();
  return;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  init();
  for (int i = 1; i <= n; i++)
    T[0].root[i] = T[0].update(T[0].root[i - 1], 1, q, a[i], dp[0][i]);
  for (int i = n; i >= 1; i--)
    T[1].root[i] = T[1].update(T[1].root[i + 1], 1, q, a[i], dp[1][i]);
  while (m--) {
    int x, h;
    scanf("%d%d", &x, &h);
    int res = book[x] ? LIS - 1 : LIS;
    int ll = 1, lr = upper_bound(b + 1, b + q + 1, h - 1) - b - 1,
        rl = lower_bound(b + 1, b + q + 1, h + 1) - b, rr = q;
    res = max(res, T[0].query(T[0].root[x - 1], 1, q, ll, lr) +
                       T[1].query(T[1].root[x + 1], 1, q, rl, rr) + 1);
    if (book[x] && cnt[dp[0][x]] > 1) res = max(res, LIS);
    printf("%d\n", res);
  }
  return 0;
}
