#include <bits/stdc++.h>
using namespace std;
template <class T>
using v2d = vector<vector<T> >;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxN = 4e5 + 10;
const int maxS = 8e5 + 10;
const int maxM = 4e5 + 10;
int n, m, h[maxN];
int dp_pre[maxN], dp_suf[maxN];
int dp_w[maxN];
int res[maxM];
vector<int> c[maxS];
int sz;
vector<int> tp;
struct query {
  int idx, a, b;
  query() {}
  query(int idx, int a, int b) : idx(idx), a(a), b(b) {}
};
vector<query> queries;
struct node {
  int max_x = 0, max_y = 0, max_val = 0;
  node() {}
} f[maxS * 4];
int idx, val, L, R;
bool type;
void update(int x, int low, int high) {
  if (low == high && low == idx) {
    if (!type) {
      f[x].max_x = val;
    } else {
      f[x].max_y = val;
    }
    f[x].max_val = max(f[x].max_x, f[x].max_y);
    return;
  }
  int mid = (low + high) / 2;
  if (idx <= mid) {
    update(x * 2, low, mid);
  } else {
    update(x * 2 + 1, mid + 1, high);
  }
  f[x].max_x = max(f[x * 2].max_x, f[x * 2 + 1].max_x);
  f[x].max_y = max(f[x * 2].max_y, f[x * 2 + 1].max_y);
  f[x].max_val = max({f[x * 2].max_val, f[x * 2 + 1].max_val,
                      f[x * 2].max_x + f[x * 2 + 1].max_y});
}
int get_max(int x, int low, int high) {
  if (low > R || high < L) {
    return 0;
  }
  if (low >= L && high <= R) {
    return (type == 0 ? f[x].max_x : f[x].max_y);
  }
  int mid = (low + high) / 2;
  return max(get_max(x * 2, low, mid), get_max(x * 2 + 1, mid + 1, high));
}
namespace FenwickTree {
const int maxN = 8e5 + 10;
int n, f[maxN];
void init(int nn) {
  n = nn;
  fill(f + 1, f + n + 1, 0);
}
void update(int x, int d) {
  for (; x <= n; x += x & -x) {
    uax(f[x], d);
  }
}
int query(int x) {
  int r = 0;
  for (; x > 0; x &= x - 1) {
    uax(r, f[x]);
  }
  return r;
}
}  // namespace FenwickTree
void solve() {
  cin >> n >> m;
  for (int i = 1; i <= (int)(n); ++i) {
    cin >> h[i];
    tp.emplace_back(h[i]);
  }
  for (int i = 1; i <= (int)(m); ++i) {
    int a, b;
    cin >> a >> b;
    tp.emplace_back(b);
    queries.emplace_back(i, a, b);
  }
  sort((tp).begin(), (tp).end());
  tp.resize(unique((tp).begin(), (tp).end()) - tp.begin());
  for (int i = 1; i <= (int)(n); ++i) {
    h[i] = lower_bound((tp).begin(), (tp).end(), h[i]) - tp.begin() + 1;
  }
  for (auto &q : queries) {
    q.b = lower_bound((tp).begin(), (tp).end(), q.b) - tp.begin() + 1;
  }
  sort((queries).begin(), (queries).end(),
       [](query x, query y) { return x.a < y.a; });
  sz = tp.size();
  FenwickTree::init(sz);
  for (int i = 1; i <= (int)(n); ++i) {
    dp_pre[i] = FenwickTree::query(h[i] - 1) + 1;
    FenwickTree::update(h[i], dp_pre[i]);
  }
  FenwickTree::init(sz);
  for (int i = n; i; --i) {
    dp_suf[i] = FenwickTree::query(sz - h[i]) + 1;
    FenwickTree::update(sz - h[i] + 1, dp_suf[i]);
    c[h[i]].emplace_back(dp_suf[i]);
    idx = h[i];
    val = dp_suf[i];
    type = 1;
    update(1, 1, sz);
  }
  int cur = 0;
  for (int i = 1; i <= (int)(n); ++i) {
    c[h[i]].pop_back();
    idx = h[i];
    val = (c[h[i]].empty() ? 0 : c[h[i]].back());
    type = 1;
    update(1, 1, sz);
    if (i > 1) {
      idx = h[i - 1];
      val = dp_pre[i - 1];
      type = 0;
      update(1, 1, sz);
    }
    dp_w[i] = f[1].max_val;
    while (cur < m && queries[cur].a == i) {
      L = 1;
      R = queries[cur].b - 1;
      type = 0;
      int l = get_max(1, 1, sz);
      L = queries[cur].b + 1;
      R = sz;
      type = 1;
      int r = get_max(1, 1, sz);
      res[queries[cur].idx] = max(dp_w[i], l + r + 1);
      ++cur;
    }
  }
  for (int i = 1; i <= (int)(m); ++i) {
    cout << res[i] << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
