#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; #define mid ((left+right)>>1) const ll inf=2e18; int n,k; ll t; ll arr[100023]; int m; ll mn[100023][17],mx[100023][17]; bool f(ll s){ s*=2*t; ll d=0; for(int i=k+1;i<=n;i++){ d+=s-(arr[i]-arr[i-1]); mx[i-k][0]=mn[i-k][0]=d; } m=n-k; for(int j=1;j<17;j++){ for(int i=0;i<=m;i++){ if(i+(1<<(j-1))>m)mn[i][j]=mn[i][j-1]; else mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); if(i+(1<<(j-1))>m)mx[i][j]=mx[i][j-1]; else mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); } } d=0; int l=0,r=0; for(int i=k;i>=1;i--){ for(int j=17-1;j>=0;j--){ if(mx[l][j]+d<0){ l+=(1<<j); l=min(l,m+1); if(l==m+1)return false; } if(r-(1<<j)+1>=0&&mx[r-(1<<j)+1][j]+d<0){ r-=(1<<j); if(r==-1)return false; } } if(l>r)return false; for(int j=17-1;j>=0;j--){ if(r==m+1)break; if(mn[r][j]+d>=0){ r+=(1<<j); r=min(r,m+1); } } r--; d+=s-(arr[i]-arr[i-1]); } return r==m; } signed main(){ ios_base::sync_with_stdio(23^23);cin.tie(0); cin>>n>>k>>t; for(int i=1;i<=n;i++){ cin>>arr[i]; } int l=1,r=1e9; while(l<r){ ll s=(l+r)/2; if(f(s))r=s; else l=s+1; } cout<<l<<endl; }