#include <bits/stdc++.h>
using namespace std;
const int tope = 1 << 21;
const int primero = 1 << 20;
int cuantos[tope][2];
int lon[tope][2];
int longitud[tope];
void anyade(int pos, int ind, int amount) {
  pos += primero;
  cuantos[pos][ind] += amount;
  lon[pos][0] = cuantos[pos][0] > 0;
  lon[pos][1] = cuantos[pos][1] > 0;
  longitud[pos] = lon[pos][0] or lon[pos][1];
  while (pos > 1) {
    pos /= 2;
    lon[pos][0] = lon[2 * pos][0] + lon[2 * pos + 1][0];
    lon[pos][1] = lon[2 * pos][1] + lon[2 * pos + 1][1];
    longitud[pos] = max(longitud[2 * pos] + lon[2 * pos + 1][1],
                        lon[2 * pos][0] + longitud[2 * pos + 1]);
  }
}
int amount = 0;
int v[tope];
int posicion(int val) {
  if (amount == 0) return 0;
  int inf = -1;
  int sup = amount;
  while (inf + 1 < sup) {
    int med = (inf + sup) / 2;
    if (val <= v[med])
      sup = med;
    else
      inf = med;
  }
  return sup;
}
int posiciondec(int val) {
  if (amount == 0) return 0;
  int inf = -1;
  int sup = amount;
  while (inf + 1 < sup) {
    int med = (inf + sup) / 2;
    if (val >= v[med])
      sup = med;
    else
      inf = med;
  }
  return sup;
}
int n, q;
int input[tope];
int valq[tope];
int sol[tope];
int len[tope];
vector<int> lista[tope];
int poner[tope];
int quitar[tope];
int main() {
  scanf("%d%d", &n, &q);
  map<int, int> mapa;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &(input[i]));
    mapa[input[i]];
  }
  for (int i = 0; i < q; i++) {
    int pos;
    scanf("%d%d", &pos, &(valq[i]));
    lista[pos].push_back(i);
    mapa[valq[i]];
  }
  {
    int i = 1;
    for (map<int, int>::iterator it = mapa.begin(); it != mapa.end(); it++, i++)
      it->second = i;
  }
  for (int i = 1; i <= n; i++) input[i] = mapa[input[i]];
  for (int i = 0; i < q; i++) valq[i] = mapa[valq[i]];
  for (int i = 1; i <= n; i++) {
    vector<int> &lis = lista[i];
    for (int j = 0; j < int(lis.size()); j++) {
      int iq = lis[j];
      int pos = posicion(valq[iq]);
      len[iq] += pos;
    }
    int pos = posicion(input[i]);
    if (pos == amount)
      amount++;
    else {
      poner[i] = v[pos];
      anyade(v[pos], 0, -1);
    }
    v[pos] = input[i];
    quitar[i] = v[pos];
    anyade(v[pos], 0, 1);
  }
  amount = 0;
  for (int i = n; i >= 1; i--) {
    anyade(quitar[i], 0, -1);
    if (poner[i]) anyade(poner[i], 0, 1);
    vector<int> &lis = lista[i];
    for (int j = 0; j < int(lis.size()); j++) {
      int iq = lis[j];
      int pos = posiciondec(valq[iq]);
      len[iq] += pos;
      sol[iq] = max(len[iq] + 1, longitud[1]);
    }
    int pos = posiciondec(input[i]);
    if (pos == amount)
      amount++;
    else
      anyade(v[pos], 1, -1);
    v[pos] = input[i];
    anyade(v[pos], 1, 1);
  }
  for (int i = 0; i < q; i++) printf("%d\n", sol[i]);
}
