#include <bits/stdc++.h>
using namespace std;
inline void read(int &first) {
  first = 0;
  while (1) {
    char ch = getchar();
    if (ch == ' ' || ch == '\n') break;
    first = first * 10 + ch - '0';
  }
}
inline void write(int first) {
  char wr[12];
  int k = 0;
  if (!first) ++k, wr[k] = '0';
  while (first) {
    ++k;
    wr[k] = char(first % 10 + '0');
    first /= 10;
  }
  for (int i = k; i >= 1; --i) putchar(wr[i]);
}
const int N = 4e5 + 5, md = 1e9 + 7;
const int T = 1e6;
int n, m, a[N], mx, cnt, dp1[N], k1[N], dp2[N], k2[N], len, kol, k = 1;
int L[N], R[N];
pair<int, int> tree[4 * T];
bool f[N];
int w[N], q[N];
vector<int> v;
map<int, int> M;
vector<pair<int, int> > l[N], r[N];
pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
  if (a.first > b.first) return a;
  if (a.first < b.first) return b;
  return make_pair(a.first, (a.second + b.second) % md);
}
pair<int, int> get(int v, int l, int r, int L, int R) {
  if (r < L || l > R) return make_pair(0, 0);
  if (l >= L && r <= R) return tree[v];
  int mid = (l + r) >> 1;
  return combine(get(v + v, l, mid, L, R), get(v + v + 1, mid + 1, r, L, R));
}
void update(int v, int l, int r, int pos, pair<int, int> q) {
  if (l == r) {
    tree[v] = combine(tree[v], q);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(v + v, l, mid, pos, q);
  else
    update(v + v + 1, mid + 1, r, pos, q);
  tree[v] = combine(tree[v + v], tree[v + v + 1]);
}
void zip() {
  sort((v).begin(), (v).end());
  M[v[0]] = 1;
  for (int i = 1; i < v.size(); ++i)
    if (v[i] != v[i - 1]) {
      ++k;
      M[v[i]] = k;
    }
  for (int i = 1; i <= n; ++i) a[i] = M[a[i]];
  for (int i = 0; i < m; ++i) w[i] = M[w[i]];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i], v.push_back(a[i]);
  for (int i = 0; i < m; ++i) {
    cin >> q[i] >> w[i];
    v.push_back(w[i]);
  }
  zip();
  for (int i = 0; i < m; ++i) {
    cin >> q[i] >> w[i];
    l[q[i] - 1].push_back(make_pair(i, w[i] - 1));
    r[q[i] + 1].push_back(make_pair(i, w[i] + 1));
    v.push_back(w[i]);
  }
  for (int i = 0; i <= n; ++i) {
    if (i) {
      pair<int, int> q = get(1, 1, T - 1, 1, a[i] - 1);
      dp1[i] = q.first + 1;
      k1[i] = q.second;
      if (!k1[i]) k1[i] = 1;
      update(1, 1, T - 1, a[i], make_pair(dp1[i], k1[i]));
      if (dp1[i] > len) len = dp1[i], kol = 0;
      if (dp1[i] == len) kol = (kol + k1[i]) % md;
    }
    for (int j = 0; j < l[i].size(); ++j) {
      int to = l[i][j].second, num = l[i][j].first;
      L[num] = get(1, 1, T - 1, 1, to).first;
    }
  }
  memset(tree, 0, sizeof tree);
  for (int i = n + 1; i >= 1; --i) {
    if (i <= n) {
      pair<int, int> q = get(1, 1, T - 1, a[i] + 1, T - 1);
      dp2[i] = q.first + 1;
      k2[i] = q.second;
      if (!k2[i]) k2[i] = 1;
      update(1, 1, T - 1, a[i], make_pair(dp2[i], k2[i]));
    }
    for (int j = 0; j < r[i].size(); ++j) {
      int to = r[i][j].second, num = r[i][j].first;
      R[num] = get(1, 1, T - 1, to, T - 1).first;
    }
  }
  for (int i = 1; i <= n; ++i)
    if (dp1[i] + dp2[i] - 1 == len && (k1[i] * 1LL * k2[i]) % md == kol)
      f[i] = 1;
  for (int j = 0; j < m; ++j) {
    int pos = q[j], first = w[j];
    int ans = len - f[pos];
    int x1 = L[j];
    int x2 = R[j];
    ans = max(ans, x1 + x2 + 1);
    cout << ans << "\n";
  }
}
