#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; struct Seg{ int n; vector<ll>mn,mx,arr; void build(int node=1,int left=1,int right=-1){ if(right==-1)right=n; if(left==right){ mn[node]=mx[node]=arr[left-1]; return; } build(node*2,left,mid); build(node*2+1,mid+1,right); mn[node]=min(mn[node*2],mn[node*2+1]); mx[node]=max(mx[node*2],mx[node*2+1]); } void init(vector<ll>Arr){ arr=Arr; n=arr.size(); mn.clear(); mx.clear(); mn.resize(n<<2,inf); mx.resize(n<<2,-inf); build(); } int l,r; ll x; int sag(int node=1,int left=1,int right=-1){ if(right==-1)right=n; if(left>r||right<l)return 0; if(left>=l&&right<=r){ if(mx[node]<x)return 0; if(left==right)return left; if(mx[node*2+1]>=x)return sag(node*2+1,mid+1,right); return sag(node*2,left,mid); } int x=sag(node*2+1,mid+1,right); if(x==0)return sag(node*2,left,mid); return x; } int en_sag(int left,int right,ll val){ l=left;r=right;x=val; if(l>r)return 0; return sag(); } int sol(int node=1,int left=1,int right=-1){ if(right==-1)right=n; if(left>r||right<l)return n+1; if(left>=l&&right<=r){ if(mn[node]>=x)return n+1; if(left==right)return left; if(mn[node*2]<x)return sol(node*2,left,mid); return sol(node*2+1,mid+1,right); } int x=sol(node*2,left,mid); if(x==n+1)return sol(node*2+1,mid+1,right); return x; } int en_sol(int left,int right,ll val){ l=left;r=right;x=val; if(l>r)return n+1; return sol(); } }; int n,k; ll t; ll arr[100023]; Seg seg; bool f(ll s){ ll o=s; s*=2*t; ll d=0; vector<ll>v; v.pb(0); for(int i=k-1;i>=1;i--){ d+=s-(arr[i+1]-arr[i]); v.pb(d); } reverse(v.begin(),v.end()); seg.init(v); v.clear(); d=0; v.pb(0); for(int i=k+1;i<=n;i++){ d+=s-(arr[i]-arr[i-1]); v.pb(d); } int p=1; while(v.size()){ ll x=v.back(); v.pop_back(); p=seg.en_sag(1,seg.en_sol(p,k,-x)-1,-x)+1; if(p==1)return false; } return p==k+1; } 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=0,r=1e9; while(l<r){ ll s=(l+r)/2; if(f(s))r=s; else l=s+1; } cout<<l<<endl; }