#include <bits/stdc++.h> using namespace std; using pii = array<int,2>; const int INF = 2e9+5; int n, p, q; int a[2005]; int f_fast(int w) { // dp and ndp static int dp[2005], ndp[2005]; for (int j = 0; j <= q; ++j) ndp[j] = p + 10; // monotonic queues implemented as vector + head index static vector<pii> sm[2005], big[2005]; static int head_sm[2005], head_big[2005]; for (int j = 0; j <= q; ++j) { sm[j].clear(); sm[j].reserve(32); head_sm[j]=0; big[j].clear(); big[j].reserve(32); head_big[j]=0; } for (int i = 1; i <= n; ++i) { // swap dp and ndp -> copy ndp into dp for (int j = 0; j <= q; ++j) { dp[j] = ndp[j]; ndp[j] = p + 10; // reset for next iteration } for (int j = 0; j <= q; ++j) { // pop front while out of w-window while (head_sm[j] < (int)sm[j].size() && a[i] - a[ sm[j][head_sm[j]][1] ] + 1 > w) ++head_sm[j]; while (head_big[j] < (int)big[j].size() && a[i] - a[ big[j][head_big[j]][1] ] + 1 > 2*w) ++head_big[j]; // pop_back while last.x < dp[j] while (!sm[j].empty() && head_sm[j] < (int)sm[j].size() && sm[j].back()[0] < dp[j]) sm[j].pop_back(); while (!big[j].empty() && head_big[j] < (int)big[j].size() && big[j].back()[0] < dp[j]) big[j].pop_back(); // push current (dp[j], i) sm[j].push_back({dp[j], i}); big[j].push_back({dp[j], i}); // take candidates if (head_sm[j] < (int)sm[j].size()) ndp[j] = min(ndp[j], sm[j][head_sm[j]][0] + 1); if (j > 0 && head_big[j-1] < (int)big[j-1].size()) ndp[j] = min(ndp[j], big[j-1][head_big[j-1]][0]); } } int ans = INF; for (int j = 0; j <= q; ++j) ans = min(ans, ndp[j]); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> p >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; if (p + q >= n) { cout << 1 << '\n'; return 0; } sort(a+1, a+n+1); int l = 1, r = a[n] - a[1] + 1, ans = r; while (l <= r) { int m = (l + r) >> 1; if (f_fast(m) <= p) { ans = m; r = m - 1; } else l = m + 1; } cout << ans << '\n'; return 0; }