#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int N, Q; cin >> N >> Q;
	vector<int> H(N); for (int& h : H) cin >> h;
 
	vector<vector<pair<int, int>>> queries(N);
	for (int q = 0; q < Q; q++) {
		int a, b; cin >> a >> b; a--;
		queries[a].emplace_back(b, q);
	}
	vector<int> ans(Q);
 
	vector<int> forwardLis(N);
	int LIS;
	{
		vector<int> buf; buf.reserve(N);
		for (int i = 0; i < N; i++) {
			for (auto q : queries[i]) {
				ans[q.second] = int(lower_bound(buf.begin(), buf.end(), q.first) - buf.begin());
			}
			auto it = lower_bound(buf.begin(), buf.end(), H[i]);
			forwardLis[i] = int(it - buf.begin());
			if (it == buf.end()) buf.push_back(H[i]);
			else *it = H[i];
		}
		LIS = int(buf.size());
	}
 
	vector<int> numCnd(LIS);
	{
		vector<int> buf; buf.reserve(N);
		for (int i = N-1; i >= 0; i--) {
			for (auto q : queries[i]) {
				ans[q.second] += int(lower_bound(buf.begin(), buf.end(), q.first, std::greater<int>()) - buf.begin());
			}
			auto it = lower_bound(buf.begin(), buf.end(), H[i], std::greater<int>());
			int backwardLis = int(it - buf.begin());
			if (it == buf.end()) buf.push_back(H[i]);
			else *it = H[i];
 
			if (forwardLis[i] + backwardLis + 1 == LIS) {
				numCnd[forwardLis[i]]++;
			} else {
				forwardLis[i] = -1;
			}
		}
	}
 
	for (int i = 0; i < N; i++) {
		int base = LIS - (forwardLis[i] != -1 && numCnd[forwardLis[i]] == 1);
		for (auto q : queries[i]) {
			ans[q.second] = max(ans[q.second]+1, base);
		}
	}
 
	for (int v : ans) { cout << v << '\n'; }
 
	return 0;
}