一句话题意的话就是给定一个序列，从中找出至少$k$个连续的元素形成子序列，使得子序列中任意两个元素差值的最小值于其长度-1的乘积最大。
题目中给出了$ 1 \leq a_i \leq m$,然后再往深处想想可以得到长度大于$m$的子序列答案一定为$0$,所以如果是DP的话就只需要把序列长度枚举到$m$就够了。
然后他们说对于长度为$x$的序列，答案不可能超过$\frac{m}{x-1}$，根据这个性质就可以根据$k$的规模进行分段处理，首先设一个常数$S$,根据本题$m$的规模把$S$设到$500$（题解上讲设为$\sqrt{m}$，但是几乎所有人都是设为了$500$，可能更方便处理）。如果$k \leq S$，就先跑一遍DP。
然后对于$k>S$的，重新设一个数组$r_x$表示对于当前枚举到的位置，距离当前最近的值为$x$的坐标，随着枚举不断更新就好了。
//UOJ 246
//by Cydiater
//2016.10.17
#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const ll MAXN=1e6+5;
const ll oo=1LL<<60;
const ll S=500;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll r[MAXN],N,M,K,a[MAXN],ans=0,minn[MAXN],pos[MAXN];
namespace solution{
void init(){
N=read();M=read();K=read();
up(i,1,N)a[i]=read();
}
void slove(){
memset(minn,0x3f,sizeof(minn));
up(len,2,S)up(st,1,N){
ll nd=st+len-1;if(nd>N)break;
cmin(minn[st],min(minn[st+1],abs(a[nd]-a[st])));
if(len>=K)cmax(ans,minn[st]*(len-1));
}
up(i,1,N){
up(j,0,S){
if(j>0)cmax(pos[j],pos[j-1]);
if(a[i]+j<=M)cmax(pos[j],r[a[i]+j]);
if(a[i]-j>=1)cmax(pos[j],r[a[i]-j]);
if(i-pos[j]>=K)cmax(ans,(i-pos[j]-1)*(j+1));
}
r[a[i]]=i;
}
}
void output(){
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
return 0;
}