https://www.luogu.com.cn/record/200156307

https://www.luogu.com.cn/article/o4hqglym

#include <bits/stdc++.h>
#define MAXN 300055
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;

int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while(ch > '9' || ch < '0') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = res * 10 + ch - '0';
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

int a[MAXN], n, q;
int lg2[MAXN];
int ST[MAXN][20];

int getm(int L, int R) {
	int len = R - L + 1;
	int t = R - (1 << lg2[len]) + 1;
	return max(ST[L][lg2[len]], ST[t][lg2[len]]);
}

void init() {
	lg2[1] = 0;
	for(int i = 2; i <= 100055; ++ i) lg2[i] = lg2[i / 2] + 1;
	for(int i = 1; i <= n; ++ i)
		ST[i][0] = a[i];
	for(int i = 1; i < 20; ++ i)
		for(int j = 1; j + (1 << i) - 1 <= n; ++ j) {
			ST[j][i] = max(ST[j][i - 1], ST[j + (1 << (i - 1))][i - 1]);
		}
}

int getdisR(int p, int r) {
	if(p == r) return 1;
	if(r == n) return r - p + 1;
	int ma = getm(p, r - 1);
	int L = r, R = n;
	while(L + 1 < R) {
		int mid = (L + R) / 2;
		if(getm(mid, n - 1) > ma) R = mid;
		else L = mid;
	}

	if(a[R] > ma) return R - p;
	else return R - p + 1;
}

int getdisL(int p, int l) {
	if(l == 1) return p - l + 1;
	if(p == l) return 1;
	int ma = getm(l + 1, p);
	int L = 1, R = l;
	while(L < R - 1) {
		int mid = (L + R) / 2;
		if(getm(1, mid) > ma) L = mid;
		else R = mid;
	}
	if(a[L] > ma) return p - L;
	else return p - L + 1;
}

void bs1(int l, int r, int k, int p, int &s, int &e) {
	int L = l, R = r + 1;
	while(L < R - 1) {
		int mid = (L + R) / 2;
		if(getdisR(p, mid) <= k) L = mid;
		else R = mid;
	}
	e = L;
	L = l - 1, R = r;
	while(L + 1 < R) {
		int mid = (L + R) / 2;
		if(getdisR(p, mid) >= k) R = mid;
		else L = mid;
	}
	s = R;
}

void bs2(int l, int r, int k, int p, int &s, int &e) {
	int L = l, R = r + 1;
	while(L < R - 1) {
		int mid = (L + R) / 2;
		if(getdisL(p, mid) >= k) L = mid;
		else R = mid;
	}
	e = L;
	L = l - 1, R = r;
	while(L + 1 < R) {
		int mid = (L + R) / 2;
		if(getdisL(p, mid) <= k) R = mid;
		else L = mid;
	}
	s = R;
}

signed main() {
	n = read(), q = read();
	for(int i = 1; i <= n; ++ i)
		a[i] = read();
	init();

	while(q --) {
		int p = read(), k = read();
		if(k == 1) {
			write(1);puts("");
			continue;
		}
		int ans1 = 0, ans2 = 0, st1 = 0, en1 = 0;
		if(n - p + 1 >= k) {
			bs1(p, n, k, p, st1, en1);
			if(en1 >= st1)
				ans1 = en1 - st1 + 1;
		}
		int st2 = 0, en2 = 0;
		if(p >= k) {
			bs2(1, p, k, p, st2, en2);
			if(en2 >= st2)
				ans2 = en2 - st2 + 1;
		}
		write(ans1 + ans2);
		puts("");
	}
	return 0;
}