#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int inf = 1e9 + 228;
const long long mod = 1e9 + 7;
const long long mod2 = 998244353;
const long double eps = 1e-14;
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
const int maxn = 8e5 + 228;
struct trie {
  vector<int> t;
  trie() { t.resize(2100000); }
  void upd(int v, int l, int r, int k, int k_new) {
    if (l == r) {
      t[v] = max(t[v], k_new);
    } else {
      int mid = (l + r) / 2;
      if (k <= mid)
        upd(v * 2, l, mid, k, k_new);
      else
        upd(v * 2 + 1, mid + 1, r, k, k_new);
      t[v] = max(t[v * 2 + 1], t[v * 2]);
    }
  }
  int get(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return t[v];
    } else if (l > qr || ql > r) {
      return 0;
    } else {
      int mid = (l + r) / 2;
      return max(get(v * 2, l, mid, ql, qr),
                 get(v * 2 + 1, mid + 1, r, ql, qr));
    }
  }
};
int lleft[maxn];
int rright[maxn];
int ans[maxn];
int ans2[maxn];
struct post {
  int x, i, t;
  post() {}
};
vector<post> posts2;
bool cmp(pair<int, int> a, pair<int, int> b) {
  if (a.first == b.first) return a.second < b.second;
  return a.first > b.first;
}
bool cmp2(post a, post b) {
  if (a.x == b.x) return a.i > b.i;
  return a.x < b.x;
}
bool cmp3(post a, post b) {
  if (a.x == b.x) return a.i < b.i;
  return a.x > b.x;
}
void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int &i : a) cin >> i;
  vector<pair<int, int> > posts(q);
  for (int i = 0; i < q; i++) cin >> posts[i].first >> posts[i].second;
  set<int> kek;
  for (int i = 0; i < q; i++) kek.insert(posts[i].second);
  for (int i = 0; i < n; i++) kek.insert(a[i]);
  map<int, int> lol;
  int cnt = 0;
  for (int i : kek) lol[i] = ++cnt;
  for (int &i : a) i = lol[i];
  for (int i = 0; i < q; i++) posts[i].second = lol[posts[i].second];
  trie t1 = trie();
  for (int i = 0; i < n; i++) {
    lleft[i] = t1.get(1, 0, maxn - 1, 0, a[i] - 1) + 1;
    t1.upd(1, 0, maxn - 1, a[i], lleft[i]);
  }
  memset(&t1.t[0], 0, sizeof(t1.t[0]) * t1.t.size());
  for (int i = n - 1; i >= 0; i--) {
    rright[i] = t1.get(1, 0, maxn - 1, a[i] + 1, maxn) + 1;
    t1.upd(1, 0, maxn - 1, a[i], rright[i]);
  }
  int mx = 0;
  for (int i = 0; i < n; i++) mx = max(mx, lleft[i] + rright[i] - 1);
  vector<pair<int, int> > lol2;
  for (int i = 0; i < n; i++) lol2.push_back(make_pair(a[i], i));
  sort(lol2.begin(), lol2.end(), cmp);
  trie t2 = trie();
  for (pair<int, int> i : lol2) {
    if (t2.get(1, 0, maxn - 1, i.second + 1, maxn - 1) + lleft[i.second] !=
        mx) {
      t2.upd(1, 0, maxn - 1, i.second, rright[i.second]);
      continue;
    }
    if (lleft[i.second] == 1 && i.second) {
      ans[0]++;
      ans[i.second]--;
    }
    if (lleft[i.second] == mx) {
      ans[i.second + 1]++;
      ans[maxn - 1]--;
    }
    int want = mx - lleft[i.second];
    int l = i.second + 1, r = n + 1;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (t2.get(1, 0, maxn - 1, m, maxn - 1) >= want)
        l = m;
      else
        r = m;
    }
    ans[i.second + 1]++;
    ans[l]--;
    t2.upd(1, 0, maxn - 1, i.second, rright[i.second]);
  }
  for (int i = 1; i <= n; i++) {
    ans[i] += ans[i - 1];
    ans[i - 1] = ans[i - 1] > 0;
  }
  for (int i = 0; i < q; i++) {
    post cur;
    cur.t = i + 1;
    cur.i = posts[i].first - 1;
    cur.x = posts[i].second;
    posts2.push_back(cur);
  }
  for (int i = 0; i < n; i++) {
    post cur;
    cur.t = 0;
    cur.i = i;
    cur.x = a[i];
    posts2.push_back(cur);
  }
  sort(posts2.begin(), posts2.end(), cmp2);
  memset(&t2.t[0], 0, sizeof(t2.t[0]) * t2.t.size());
  for (post i : posts2) {
    if (i.t == 0) {
      t2.upd(1, 0, maxn - 1, i.i, lleft[i.i]);
      continue;
    }
    ans2[i.t - 1] += t2.get(1, 0, maxn - 1, 0, i.i - 1);
  }
  reverse(posts2.begin(), posts2.end());
  memset(&t2.t[0], 0, sizeof(t2.t[0]) * t2.t.size());
  for (post i : posts2) {
    if (i.t == 0) {
      t2.upd(1, 0, maxn - 1, i.i, rright[i.i]);
      continue;
    }
    ans2[i.t - 1] += t2.get(1, 0, maxn - 1, i.i + 1, maxn - 1);
  }
  for (int i = 0; i < q; i++) {
    cout << max({mx - 1, ans[posts[i].first - 1] * mx, ans2[i] + 1}) << '\n';
  }
}
signed main() {
  fast_io();
  cout << fixed << setprecision(10);
  int q = 1;
  while (q--) solve();
}
