infoarena

void rezolvare()
	{
	int i,j,p,q;
	p=1; q=0; //initial coada este goala
	for(i=1;i<=n;i++)
		{
		while(p<=q&&v[d[q]]<=v[i]) q--; //cat timp am varsta mai mare de adaugat
		d[++q]=i; //il punem in deque
		if(i-d[p]>k) p++; //dispare primul element
		j=v[d[p]]-v[i]; //diferenta dintre cel mai batran solarian din interval, si solarianul curent
		if(j>vmax) vmax=j; //am gasit o diferenta mai mare
		}
	}

	FirstMax = 1, LastMax = 0; // DequeMax e goala
	FirstMin = 1, LastMin = 0; // DequeMin e goala
	
	for(i = 1; i <= N; i ++)
	{
		while(Values[i] >= Values[DequeMax[LastMax]] && LastMax >= FirstMax) LastMax --;
		DequeMax[++ LastMax] = i;
		if(abs(i - DequeMax[FirstMax]) > K) // conditia de vecini
			FirstMax ++;
		
		while(Values[i] <= Values[DequeMin[LastMin]] && LastMin >= FirstMin) LastMin --;
		DequeMin[++ LastMin] = i;
		if(abs(i - DequeMin[FirstMin]) > K) // conditia de vecini
			FirstMin ++;
		
		if(Values[DequeMax[FirstMax]] - Values[DequeMin[FirstMin]] > maxim)
				maxim = Values[DequeMax[FirstMax]] - Values[DequeMin[FirstMin]]; //cel mai mare element din secventa - cel mai mic element din secventa
	}

#include <fstream>
#include <cstdlib>
using namespace std;
 
ifstream fin("vila2.in");
ofstream fout("vila2.out");

int n,k,front,back,i,maxim,front1,back1;
int a[100010],d[100010],d1[100010];
 
int main()
{
maxim=-30001;
    
    fin>>n>>k;
    for(i=1;i<=n;i++){
        fin>>a[i];	
    }
     
    front=1,back=0;
	front1=1,back1=0;
     
    for(i=1;i<=n;i++){
         
        while(front<=back && a[i]>=a[d[back]])
            back--;
		d[++back]=i;
		while(front1<=back1 && a[i]<=a[d1[back1]] )
            back1--;
		d1[++back1]=i;

       if(i>=k &&  a[d[front]]-a[d1[front1]]>maxim && abs(d[back]-d1[back1])<=k){
            maxim=a[d[front]]-a[d1[front1]];
        }
       if(d[front] == i-k)
           front++;
	   if(d[front1] == i-k)
           front1++;
   }
     
   fout<<maxim;
     
  return 0;
}