#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; vl l_dif; vl r_dif; bool check(ll speed) { speed *= T; int l_ptr = 0; int r_ptr = 0; ll cur_power = speed; while(l_ptr < siz(l_dif) || r_ptr < siz(r_dif)) { if(r_ptr == siz(r_dif) || (l_ptr != siz(l_dif) && l_dif[l_ptr] < r_dif[r_ptr])) { if(cur_power < l_dif[l_ptr]/2) return 0; cur_power += -l_dif[l_ptr]/2+speed; l_ptr++; } else { if(cur_power < r_dif[r_ptr]/2) return 0; cur_power += -r_dif[r_ptr]/2+speed; r_ptr++; } } return 1; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,k; cin >> n >> k >> T; vl arr(n); rep(i,n) cin >> arr[i]; rep(i,n) arr[i] *= 2; T *= 2; rep(i,k-1) l_dif.pb(arr[i+1]-arr[i]); reverse(all(l_dif)); rep2(i,k-1,n-2) r_dif.pb(arr[i+1]-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"; }