#ifdef __AVX2__ #pragma GCC target "avx2" #endif #pragma GCC optimize "O3" #pragma GCC optimize "unroll-loops" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define elif else if #define all(l) begin(l),end(l) #define rall(l) rbegin(l),rend(l) #define append push_back #define print(l) for(auto i:l) cout<<i<<' '; cout<<endl; #define pprint(a,b) cout<<a<<' '<<b<<endl; #define inp(l) for(auto &i:l) cin>>i; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define pai make_pair #define endl "\n" #define pii pair<int,int> #define fi first #define se second #define vec vector // const int mod=998244353; const int mod1=998244353; const int mod=1e9+7; const int N=2e5+5; int iter=1,itera=1; void solve(){ int n,p,q; cin>>n>>p>>q; p=min(p,n); vec<int>a(n); inp(a); a.insert(begin(a),-1e18); sort(all(a)); map<int,int>d; for(auto i:a) d[i]=1e18; for(int i=0;i<=n;i++) d[a[i]]=min(d[a[i]],i); int l=0,r=1e15; while(l+1<r){ int m=(l+r)/2; vec<vec<int>>dp(n+1,vec<int>(p+1,1e15)); dp[0][0]=0; for(int i=1;i<=n;i++){ int x=d[*(lower_bound(all(a),a[i]-2*m+1))]; int y=d[*(lower_bound(all(a),a[i]-m+1))]; // cout<<i<<' '<<x<<' '<<y<<endl; for(int j=0;j<=p;j++){ dp[i][j]=dp[x-1][j]+1; if(j!=0) dp[i][j]=min(dp[i][j],dp[y-1][j-1]); } } bool f=0; for(int j=0;j<=p;j++){ if(dp[n][j]<=q) f=1; } if(f) r=m; else l=m; // break; } cout<<r<<endl; } signed main(){ // freopen("","r",stdin); // freopen("","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<<fixed<<setprecision(20); // cin>>itera; for(iter=1;iter<=itera;iter++) solve(); }