提供一种极限卡过的方法(O(nlogn)做法）

#include <cstdio>
#include <cstring>
using namespace std;
int a[3000005];
int maxn[3000005],minn[3000005];
int q1[3000005],q2[3000005];
int main(){
	int n,dis;
	scanf("%d %d",&dis,&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int l=0,r=n,res=0;
	while(l<=r){
		int k=(l+r)/2;
		int head1=1,tail1=1,head2=1,tail2=1;
		q1[tail1]=q2[tail2]=1;
		for(int i=2;i<=n;i++){
			while(head1<=tail1 and i-q1[head1]>=k) head1++;
			while(head2<=tail2 and i-q2[head2]>=k) head2++;
			while(head1<=tail1 and a[q1[tail1]]<=a[i]) tail1--;
			while(head2<=tail2 and a[q2[tail2]]>=a[i]) tail2--;
			q1[++tail1]=i,q2[++tail2]=i;
			maxn[i]=q1[head1],minn[i]=q2[head2]; 
		}
		bool flag=0;
		for(int i=k;i<=n;i++)if(a[maxn[i]]-a[minn[i]]<=dis)flag=1;
		if(flag){
			res=k;
			l=k+1;
		}
		else r=k-1;
	}
	printf("%d\n",res);
}