#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 NMAX1 = 4e3;
using namespace std;
int cost[NMAX1 + 5][NMAX1 + 5], dp[NMAX1 + 5][NMAX1 + 5];
int a[NMAX + 5], pre[NMAX + 5], suf[NMAX + 5], n, d, t;
struct LazySeg {
pair<int, int> aint[4 * NMAX + 5];
int lazy[4 * NMAX + 5];
inline pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
if (a.fi != b.fi) return min(a, b);
return {a.fi, a.se + b.se};
}
void build(int nod = 1, int st = 1, int dr = n) {
if (st == dr) {
aint[nod] = {0, 1};
lazy[nod] = 0;
return;
}
int m = (st + dr) >> 1;
build(2 * nod, st, m);
build(2 * nod + 1, m + 1, dr);
lazy[nod] = 0;
aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}
void push(int nod, int st, int dr){
if (lazy[nod] != 0) {
aint[nod].fi += lazy[nod];
if (st != dr) {
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
}
void range_add(int l, int r, int v, int nod = 1, int st = 1, int dr = n) {
push(nod, st, dr);
if (st > r || dr < l) return;
if (l <= st && dr <= r) {
lazy[nod] += v;
push(nod, st, dr);
return;
}
int m = (st + dr) >> 1;
range_add(l, r, v, 2 * nod, st, m);
range_add(l, r, v, 2 * nod + 1, m + 1, dr);
aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}
pair<int, int> query(int l, int r, int nod = 1, int st = 1, int dr = n) {
push(nod, st, dr);
if (st > r || dr < l) return {INT_MAX, 0};
if (l <= st && dr <= r) return aint[nod];
int m = (st + dr) >> 1;
return merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
}
};
LazySeg aint;
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) {
if (dp[i - 1][used - 1] + cost[i][m] < dp[m][used]) {
dp[m][used] = dp[i - 1][used - 1] + cost[i][m];
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 (d == 1) {
aint.build();
for (int i = 1; i <= n; ++i) {
if (a[i] < t)
aint.range_add(i, min(n, i + t - a[i]), 1);
auto [mn, ap] = aint.query(1, i);
pre[i] = i - (mn != 0 ? 0 : ap);
}
for (int i = 1; i <= n; ++i) {
auto [mn, ap] = aint.query(i, n);
suf[i] = (n - i + 1) - (mn != 0 ? 0 : ap);
if (a[i] <= t)
aint.range_add(i, min(n, i + t - a[i]), -1);
}
int ans = pre[n];
for (int perete = 1; perete <= n - 1; ++perete)
ans = min(ans, pre[perete] + suf[perete + 1]);
cout << ans << '\n';
exit(0);
}
// if (n <= 500) {
// for (int l = 1; l <= n; ++l) {
// aint.build();
// for (int r = l; r <= n; ++r) {
// if (a[r] <= t)
// aint.range_add(r, min(n, r + t - a[r]), 1);
// auto [mn, ap] = aint.query(l, r);
// cost[l][r] = (r - l + 1) - (mn != 0 ? 0 : ap);
// }
// }
//
// fill(&dp[0][0], &dp[0][0] + (NMAX1 + 5) * (NMAX1 + 5), INT_MAX);
// d = min(d, n + 2);
// dp[0][0] = 0;
// for (int i = 1; i <= n; ++i) {
// for (int used = 0; used <= d; ++used) {
// if (used == 0) {
// dp[i][used] = cost[1][i];
// continue;
// }
//
// for (int j = 0; j <= i - 1; ++j)
// dp[i][used] = min(dp[i][used], dp[j][used - 1] + cost[j + 1][i]);
// }
// }
//
// cout << *min_element(dp[n], dp[n] + d + 1) << '\n';
// exit(0);
// }
if (n <= 4000) {
// for (int l = 1; l <= n; ++l) {
// aint.build();
// for (int r = l; r <= n; ++r) {
// if (a[r] <= t)
// aint.range_add(r, min(n, r + t - a[r]), 1);
// auto [mn, ap] = aint.query(l, r);
// cost[l][r] = (r - l + 1) - (mn != 0 ? 0 : ap);
// }
// }
mt19937 rng(time(NULL));
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
cost[i][j] = 1 + (rng() % n);
for (int i = 1; i <= n; ++i)
dp[i][0] = cost[1][i];
d = min(d, n - 1);
for (int layer = 1; layer <= d; ++layer)
divide(layer);
cout << *min_element(dp[n], dp[n] + d + 1) << '\n';
}
return 0;
}
