#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e4 + 5, Q = 2e5 + 5;
int tr[N];
void upd(int x) { while (x < N) tr[x]++, x += x & -x; }
int ask(int x) { int r = 0; while (x) r += tr[x], x -= x & -x; return r; }
int n, q, a[N], B;
int answer[Q];
vector<array<int, 2>> que[N];
struct young {
	bool typ;
	vector<int> young[N];
	int num;
	void insert(int x) {
		for (int i = 1; i <= B; i++) {
			int id;
			if (!typ) id = lower_bound(young[i].begin(), young[i].end(), x) - young[i].begin();
			else id = upper_bound(young[i].begin(), young[i].end(), x) - young[i].begin();
			if (id == young[i].size()) {
				young[i].push_back(x);
				if (!typ) upd(young[i].size());
				else if (young[i].size() > B) upd(i);
				break;
			}
			swap(x, young[i][id]);
		}
	}
} t1, t2;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q, B = sqrt(n);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= q; i++) {
		int m, k;
		cin >> m >> k;
		que[m].push_back({k, i});
	}
	t2.typ = 1;
	for (int i = 1; i <= n; i++) {
		t1.insert(a[i]);
		t2.insert(N - a[i]);
		for (auto [m, id] : que[i]) {
			answer[id] = ask(m);
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << answer[i] << "\n";
	}
	return 0;
}