#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const double pi = 3.1415926535897932, eps = 1e-6;
void chmax(int &x, int y) {
  if (x < y) x = y;
}
void chmin(int &x, int y) {
  if (x > y) x = y;
}
struct segtree {
  int dat[2097200], n;
  void build(int nn) {
    n = 1;
    while (n <= nn) n <<= 1;
  }
  void update(int k, int a) {
    k += n - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = max(dat[(k << 1) + 1], dat[(k << 1) + 2]);
    }
  }
  int query(int l, int r) { return query(l, r + 1, 0, 0, n); }
  int query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return -inf;
    if (a <= l && r <= b) return dat[k];
    return max(query(a, b, (k << 1) + 1, l, (l + r) >> 1),
               query(a, b, (k << 1) + 2, (l + r) >> 1, r));
  }
} seg;
int n, a[400005], m, cnt, al[400005], ar[400005], ansl[400005], ansr[400005],
    ljy[800005];
bool sat[400005];
pair<int, int> qu[400005];
vector<pair<int, int> > q[400005];
map<int, int> wbh;
bool good[400005];
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = (1); (i) <= (n); (i)++) scanf("%d", a + i), wbh[a[i]] = 666;
  for (int(i) = (1); (i) <= (m); (i)++) {
    scanf("%d%d", &qu[i].first, &qu[i].second);
    q[qu[i].first].push_back(make_pair(i, qu[i].second));
    wbh[qu[i].second] = 666;
  }
  for (map<int, int>::iterator it = wbh.begin(); it != wbh.end(); it++)
    it->second = ++cnt;
  seg.build(cnt + 1);
  for (int(i) = (1); (i) <= (n); (i)++) sort(q[i].begin(), q[i].end());
  for (int(i) = (1); (i) <= (n); (i)++) {
    for (int(j) = (0); (j) < (q[i].size()); (j)++)
      q[i][j].second = wbh[q[i][j].second];
  }
  for (int(i) = (1); (i) <= (n); (i)++) a[i] = wbh[a[i]];
  for (int(i) = (1); (i) <= (n); (i)++) {
    for (int(j) = (0); (j) < (q[i].size()); (j)++) {
      int u = q[i][j].second, id = q[i][j].first;
      int xh = seg.query(0, u - 1);
      ansl[id] = xh + 1;
    }
    al[i] = seg.query(0, a[i] - 1) + 1;
    seg.update(a[i], al[i]);
  }
  int u = -1;
  for (int(i) = (1); (i) <= (n); (i)++) u = max(u, al[i]);
  for (int(i) = (0); (i) <= (seg.n + seg.n); (i)++) seg.dat[i] = 0;
  for (int(i) = (n); (i) >= (1); (i)--) {
    for (int(j) = (0); (j) < (q[i].size()); (j)++) {
      int u = q[i][j].second, id = q[i][j].first;
      int xh = seg.query(u + 1, cnt + 1);
      ansr[id] = xh + 1;
    }
    ar[i] = seg.query(a[i] + 1, cnt + 1) + 1;
    seg.update(a[i], ar[i]);
  }
  for (int(i) = (1); (i) <= (n); (i)++) {
    if (al[i] + ar[i] == u + 1) {
      sat[i] = 1;
      ljy[al[i]]++;
    }
  }
  for (int(i) = (1); (i) <= (n); (i)++) {
    if (sat[i]) {
      if (ljy[al[i]] == 1)
        good[i] = 0;
      else
        good[i] = 1;
    }
  }
  for (int(i) = (1); (i) <= (m); (i)++) {
    int x = qu[i].first, y = qu[i].second;
    int cur = ansl[i] + ansr[i] - 1;
    if (sat[x])
      cur = max(cur, u - 1 + good[x]);
    else
      cur = max(cur, u);
    printf("%d\n", cur);
  }
  return 0;
}
