There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

For each test case, print the length of the subsequence on a single line.

维护两个单调队列，一个单调递增，维护最小值，一个单调递减，维护最大值。

#include<stdio.h>#include<string.h>const int maxn = 100005;int a[maxn],q1[maxn],q2[maxn];int main(){	int n,m,k;	while (~scanf("%d%d%d",&n,&m,&k))	{		int res = 0,pos = 0;		memset(a,0,sizeof(a));		memset(q1,0,sizeof(q1));		memset(q2,0,sizeof(q2));		for (int i = 1;i <= n;i++)	scanf("%d",&a[i]);		int head1 = 1,head2 = 1,tail1 = 0,tail2 = 0;		for (int i = 1;i <= n;i++)		{			while (head1 <= tail1 && a[i] <= a[q1[tail1]])	tail1--;  //队头元素最小 			q1[++tail1] = i;			while (head2 <= tail2 && a[i] >= a[q2[tail2]])	tail2--;  //队头元素最大 			q2[++tail2] = i;			while (head1 <= tail1 && head2 <= tail2 && a[q2[head2]] - a[q1[head1]] > k)			{				if (q1[head1]<q2[head2])	pos = q1[head1++];				else	pos = q2[head2++];			}			if (head1 <= tail1 && head2 <= tail2 && a[q2[head2]] - a[q1[head1]] >= m)	res = res>(i-pos)?res:(i-pos);					}		printf("%d\n",res);	}	return 0;}