#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400100;
const int offset = (1 << 20);
const int MOD = 1e9 + 7;
int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}
int mul(int x, int y) { return (long long)x * y % MOD; }
struct tournament {
  pair<int, int> p[offset * 2];
  void init() {
    for (int i = (0); i < int(offset * 2); i++) p[i] = make_pair(0, 0);
  }
  pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    pair<int, int> ret = a;
    if (ret.first == b.first) ret.second = add(ret.second, b.second);
    if (ret.first < b.first) ret = b;
    return ret;
  }
  void update(int x, int a, int b) {
    x += offset;
    p[x] = merge(p[x], make_pair(a, b));
    x /= 2;
    while (x) {
      p[x] = merge(p[x * 2], p[x * 2 + 1]);
      x /= 2;
    }
  }
  pair<int, int> get(int cvor, int l, int r, int a, int b) {
    if (l > b || r < a) return make_pair(0, 0);
    if (l >= a && r <= b) return p[cvor];
    int mid = (l + r) / 2;
    pair<int, int> x = get(cvor * 2, l, mid, a, b);
    pair<int, int> y = get(cvor * 2 + 1, mid + 1, r, a, b);
    return merge(x, y);
  }
} T;
int n, m, p[MAXN], cnt_left[MAXN], cnt_right[MAXN];
int dp_pref[MAXN], dp_suff[MAXN];
int ans[MAXN];
int pref[MAXN], suff[MAXN];
int N, M;
int a[MAXN], b[MAXN];
vector<pair<int, int> > v[MAXN];
int get(int x) {
  if (pref[x] + suff[x] - 1 != N) return N;
  return N - (mul(cnt_left[x], cnt_right[x]) == M);
}
void sazmi() {
  vector<int> v;
  for (int i = (0); i < int(n); i++) v.push_back(p[i]);
  for (int i = (0); i < int(m); i++) v.push_back(b[i]);
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
  for (int i = (0); i < int(n); i++)
    p[i] = lower_bound((v).begin(), (v).end(), p[i]) - v.begin() + 1;
  for (int i = (0); i < int(m); i++)
    b[i] = lower_bound((v).begin(), (v).end(), b[i]) - v.begin() + 1;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = (0); i < int(n); i++) scanf("%d", &p[i]);
  for (int i = (0); i < int(m); i++) scanf("%d %d", &a[i], &b[i]);
  sazmi();
  for (int i = (0); i < int(m); i++) v[a[i] - 1].push_back(make_pair(b[i], i));
  T.init();
  for (int i = (0); i < int(n); i++) {
    for (int j = (0); j < int((int)v[i].size()); j++)
      dp_pref[v[i][j].second] =
          T.get(1, 0, offset - 1, 0, v[i][j].first - 1).first;
    pair<int, int> upd = T.get(1, 0, offset - 1, 0, p[i] - 1);
    if (upd.first == 0)
      cnt_left[i] = 1;
    else
      cnt_left[i] = upd.second;
    pref[i] = add(upd.first, 1);
    T.update(p[i], add(upd.first, 1), cnt_left[i]);
    if (N < add(upd.first, 1)) {
      N = add(upd.first, 1);
      M = 0;
    }
    if (N == add(upd.first, 1)) M = add(M, cnt_left[i]);
  }
  T.init();
  for (int i = n - 1; i >= 0; i--) {
    for (int j = (0); j < int((int)v[i].size()); j++)
      dp_suff[v[i][j].second] =
          T.get(1, 0, offset - 1, v[i][j].first + 1, offset - 1).first;
    pair<int, int> upd = T.get(1, 0, offset - 1, p[i] + 1, offset - 1);
    if (upd.first == 0)
      cnt_right[i] = 1;
    else
      cnt_right[i] = upd.second;
    suff[i] = add(upd.first, 1);
    T.update(p[i], add(upd.first, 1), cnt_right[i]);
  }
  for (int i = (0); i < int(m); i++)
    ans[i] = max(dp_pref[i] + dp_suff[i] + 1, get(a[i] - 1));
  for (int i = (0); i < int(m); i++) printf("%d\n", ans[i]);
  return 0;
}
