#include <bits/stdc++.h> using namespace std; #define ll long long const int INF = 2e9 + 5; static int dp[2005], ndp[2005], a[2005]; int n, p, q; struct MQ { vector<int> val; vector<int> id; int head, tail; void init(int cap) { val.assign(cap, 0); id.assign(cap, 0); head = tail = 0; } inline void clear() { head = tail = 0; } inline bool empty() const { return head == tail; } inline int front_val() const { return val[head]; } inline int front_id() const { return id[head]; } inline void pop_front() { ++head; } inline void push_back(int v, int idx) { while (tail > head && val[tail - 1] < v) --tail; val[tail] = v; id[tail] = idx; ++tail; } inline void pop_back_while_less_than(int x) { while (tail > head && val[tail - 1] < x) --tail; } }; int f_w(int w, vector<MQ> &sm, vector<MQ> &big) { int sentinel = INF; for (int i = 0; i <= q; ++i) ndp[i] = sentinel; ndp[0] = 0; for (int i = 0; i <= q; ++i) { sm[i].clear(); big[i].clear(); } for (int i = 1; i <= n; ++i) { // dp <- ndp, reset ndp memcpy(dp, ndp, (q + 1) * sizeof(int)); for (int j = 0; j <= q; ++j) ndp[j] = sentinel; for (int j = 0; j <= q; ++j) { // remove outdated by value comparisons (use a[id]) while (!sm[j].empty() && a[i] - a[ sm[j].front_id() ] + 1 > w) sm[j].pop_front(); while (!big[j].empty() && a[i] - a[ big[j].front_id() ] + 1 > 2 * w) big[j].pop_front(); // maintain monotonicity vs dp[j] sm[j].pop_back_while_less_than(dp[j]); big[j].pop_back_while_less_than(dp[j]); // push current dp at index i sm[j].push_back(dp[j], i); big[j].push_back(dp[j], i); // transitions if (!sm[j].empty()) ndp[j] = min(ndp[j], sm[j].front_val() + 1); if (j > 0 && !big[j - 1].empty()) ndp[j] = min(ndp[j], big[j - 1].front_val()); } } int ans = INF; for (int i = 0; i <= q; ++i) ans = min(ans, ndp[i]); return ans; } void solve() { 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; } // keep your original behavior sort(a + 1, a + n + 1); int cap = n + 5; vector<MQ> sm(q + 1), big(q + 1); for (int j = 0; j <= q; ++j) { sm[j].init(cap); big[j].init(cap); } int l = 0, r = a[n] - a[1] + 1; // allow 0 width int ans = r; while (l <= r) { int m = (l + r) >> 1; if (f_w(m, sm, big) <= p) { ans = m; r = m - 1; } else l = m + 1; } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); return 0; }