#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0;
  char ch = ' ';
  bool flag = false;
  while (!isdigit(ch)) {
    if (ch == '-') flag = true;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + (ch ^ '0');
    ch = getchar();
  }
  return flag ? -x : x;
}
struct Query {
  int num;
  int a;
  int b;
  int ans;
  Query() {}
  Query(int _x, int _y, int _num) {
    a = _x;
    b = _y;
    num = _num;
    ans = 0;
  }
};
const int MAX_N = 400005;
int bit_size;
struct BIT {
  int bit[MAX_N * 2];
  void init() { memset(bit, 0, sizeof(bit)); }
  void modify(int i, int x) {
    while (i <= bit_size) {
      bit[i] = max(bit[i], x);
      i += ((i) & (-(i)));
    }
  }
  int query(int i) {
    int ans = 0;
    while (i > 0) {
      ans = max(ans, bit[i]);
      i -= ((i) & (-(i)));
    }
    return ans;
  }
} bit;
const int INF = 0x3f3f3f3f;
Query zip[MAX_N];
int n, m;
int h[MAX_N];
int Lis_L[MAX_N];
int Lis_R[MAX_N];
int query[MAX_N];
int pos_Lis[MAX_N];
int cnt_pos[MAX_N];
int len_Lis;
bool comp1(Query a1, Query a2) { return a1.a < a2.a; }
bool comp2(Query a1, Query a2) { return a1.num < a2.num; }
void calc_Lis_L() {
  vector<int> ans;
  ans.assign(n, INF);
  for (int i = 1; i <= n; i++) {
    int pos = lower_bound(ans.begin(), ans.end(), h[i]) - ans.begin();
    ans[pos] = h[i];
    Lis_L[i] = pos + 1;
    len_Lis = max(len_Lis, pos + 1);
  }
}
void calc_Lis_R() {
  vector<int> ans;
  ans.assign(n, INF);
  for (int i = n; i >= 1; i--) {
    int pos = lower_bound(ans.begin(), ans.end(), -h[i]) - ans.begin();
    ans[pos] = -h[i];
    Lis_R[i] = pos + 1;
  }
}
void overall_hashing() {
  map<int, int> Find;
  for (int i = 0; i < m; i++) Find[zip[i].b]++;
  for (int i = 1; i <= n; i++) Find[h[i]]++;
  int cnt = 0;
  for (map<int, int>::iterator it = Find.begin(); it != Find.end(); it++) {
    it->second = ++cnt;
  }
  bit_size = Find.size();
  for (int i = 0; i < m; i++) zip[i].b = Find[zip[i].b];
  for (int i = 1; i <= n; i++) h[i] = Find[h[i]];
}
void calc_pos_Lis() {
  memset(pos_Lis, -1, sizeof(pos_Lis));
  for (int i = 1; i <= n; i++) {
    if (Lis_L[i] + Lis_R[i] - 1 == len_Lis) {
      pos_Lis[i] = Lis_L[i];
      cnt_pos[pos_Lis[i]]++;
    }
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) h[i] = read();
  for (int i = 1; i <= m; i++) {
    int a = read(), b = read();
    zip[i - 1] = (Query(a, b, i));
  }
  overall_hashing();
  calc_Lis_L();
  calc_Lis_R();
  calc_pos_Lis();
  for (int i = 0; i < m; i++) {
    if (pos_Lis[zip[i].a] == -1 || cnt_pos[pos_Lis[zip[i].a]] > 1)
      zip[i].ans = len_Lis;
    else
      zip[i].ans = len_Lis - 1;
  }
  sort(zip, zip + m, comp1);
  bit.init();
  int pos = 0;
  for (int i = 1; i <= n; i++) {
    while (pos < m - 1 && zip[pos].a < i) pos++;
    while (pos < m && zip[pos].a == i) {
      query[pos] += bit.query(zip[pos].b - 1);
      pos++;
    }
    bit.modify(h[i], Lis_L[i]);
  }
  pos = m - 1;
  bit.init();
  for (int i = n; i >= 1; i--) {
    while (pos > 0 && zip[pos].a > i) pos--;
    while (pos >= 0 && zip[pos].a == i) {
      query[pos] += bit.query(bit_size - zip[pos].b);
      pos--;
    }
    bit.modify(bit_size - h[i] + 1, Lis_R[i]);
  }
  for (int i = 0; i < m; i++) {
    zip[i].ans = max(zip[i].ans, query[i] + 1);
  }
  sort(zip, zip + m, comp2);
  for (int i = 0; i < m; i++) {
    cout << zip[i].ans << endl;
  }
  return 0;
}
