#include <bits/stdc++.h>
// #define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int NMAX = 2e6;
const int NMAX23 = 4e3;
using namespace std;
vector<int> dp[NMAX + 5];
int cost[NMAX23 + 5][NMAX23 + 5];
int a[NMAX + 5], pre[NMAX + 5], suf[NMAX + 5], n, d, t;
namespace PersistentSeg {
using pii = pair<int,int>;
struct Node {
pii val;
int lazy;
Node *l, *r;
};
const int MAXNODES = 8e6;
Node pool[MAXNODES];
int ptr = 0;
Node* new_node(pii val = {0,0}, int lazy = 0, Node* l = nullptr, Node* r = nullptr) {
Node* n = &pool[ptr++];
n->val = val;
n->lazy = lazy;
n->l = l;
n->r = r;
return n;
}
pii merge(pii a, pii b) {
if (a.first != b.first) return min(a, b);
return {a.first, a.second + b.second};
}
Node* build(int st, int dr) {
if (st == dr) {
return new_node({0,1}, 0, nullptr, nullptr);
}
int m = (st + dr) >> 1;
Node* left = build(st, m);
Node* right = build(m+1, dr);
return new_node(merge(left->val, right->val), 0, left, right);
}
Node* push(Node* node, int st, int dr) {
if (node->lazy == 0) return node;
Node* res = new_node(node->val, node->lazy, node->l, node->r);
res->val.first += res->lazy;
if (st != dr) {
res->l = new_node(res->l->val, res->l->lazy, res->l->l, res->l->r);
res->r = new_node(res->r->val, res->r->lazy, res->r->l, res->r->r);
res->l->lazy += res->lazy;
res->r->lazy += res->lazy;
}
res->lazy = 0;
return res;
}
Node* range_add(Node* node, int st, int dr, int l, int r, int val) {
node = push(node, st, dr);
if (dr < l || st > r) return node;
Node* res = new_node(node->val, node->lazy, node->l, node->r);
if (l <= st && dr <= r) {
res->lazy += val;
return push(res, st, dr);
}
int m = (st + dr) >> 1;
res->l = range_add(res->l, st, m, l, r, val);
res->r = range_add(res->r, m+1, dr, l, r, val);
res->val = merge(res->l->val, res->r->val);
return res;
}
pii query(Node* node, int st, int dr, int l, int r) {
node = push(node, st, dr);
if (dr < l || st > r) return {INT_MAX, 0};
if (l <= st && dr <= r) return node->val;
int m = (st + dr) >> 1;
return merge(
query(node->l, st, m, l, r),
query(node->r, m+1, dr, l, r)
);
}
}
using namespace PersistentSeg;
Node* T[NMAX + 5];
int cost_(int l, int r) {
if (n <= 4000 && cost[l][r] != -1) return cost[l][r];
auto [mn, ap] = PersistentSeg::query(T[l], 1, n, l, r);
int res = (r - l + 1) - (mn == 0 ? ap : 0);
if (n <= 4000) cost[l][r] = res;
return res;
}
void divide(int used, int l = 1, int r = n, int optL = 1, int optR = n) {
if (l > r) return;
int m = (l + r) >> 1;
int opt = optL;
dp[m][used] = INT_MAX;
for (int i = optL; i <= min(m, optR); ++i) {
int c = cost_(i, m);
if (dp[i - 1][used - 1] + c < dp[m][used]) {
dp[m][used] = dp[i - 1][used - 1] + c;
opt = i;
}
}
divide(used, l, m - 1, optL, opt);
divide(used, m + 1, r, opt, optR);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> d >> t;
for (int i = 1; i <= n; ++i)
cin >> a[i];
if (n <= 4000) {
for (int l = 1; l <= n; ++l)
for (int r = l; r <= n; ++r)
cost[l][r] = -1;
}
d = min(d, n - 1);
for (int i = 0; i <= n; ++i)
dp[i].resize(d + 5);
T[1] = build(1, n);
for (int i = 1; i <= n; ++i) {
if (a[i] <= t)
T[1] = PersistentSeg::range_add(T[1], 1, n, i, min(n, i + t - a[i]), 1);
}
for (int i = 1; i <= n - 1; ++i) {
T[i + 1] = T[i];
if (a[i] <= t)
T[i + 1] = PersistentSeg::range_add(T[i], 1, n, i, min(n, i + t - a[i]), -1);
}
for (int i = 1; i <= n; ++i)
dp[i][0] = cost_(1, i);
for (int layer = 1; layer <= d; ++layer)
divide(layer);
cout << *min_element(dp[n].begin(), dp[n].begin() + d + 1) << '\n';
return 0;
}
