#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll T; int n,k; ll arr[100001]; ll val[100001]; bool check2(vl L, vl R) { int ptrL = 0; int ptrR = 0; ll maxL = L[0]; ll minR = R[0]; if(maxL < minR) return 0; while(ptrL != siz(L)-1 || ptrR != siz(R)-1) { bool was = 0; while(ptrL < siz(L)-1 && L[ptrL+1] >= minR) { was = 1; maxL = max(maxL,L[++ptrL]); } while(ptrR < siz(R)-1 && R[ptrR+1] <= maxL) { was = 1; minR = min(minR,R[++ptrR]); } if(!was) return 0; } return 1; } bool check(ll speed) { rep(i,n) val[i] = arr[i]-2*(ll)i*T*speed; pll bestR = {1e18,-1}; pll bestL = {-1e18,-1}; rep2(i,0,k) bestL = max(bestL,{val[i],i}); rep2(i,k,n-1) bestR = min(bestR,{val[i],i}); vl L1,L2,R1,R2; for(int i = k; i >= bestL.ss; i--) L1.pb(val[i]); rep2(i,0,bestL.ss) L2.pb(val[i]); rep2(i,k,bestR.ss) R1.pb(val[i]); for(int i = n-1; i >= bestR.ss; i--) R2.pb(val[i]); return check2(L1,R1) && check2(L2,R2); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); cin >> n >> k >> T; k--; rep(i,n) cin >> arr[i]; ll l = 0; ll r = 3e9; ll ans = -1; while(l <= r) { ll mid = (l+r)/2; if(check(mid)) { ans = mid; r = mid-1; } else { l = mid+1; } } cout << ans << "\n"; }