#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 2e6 + 11;
int a[N];
int ps[N];
vector<int> rm[N];
struct range{
int l, r;
};
struct SegTree{
int t[1 << 22], lz[1 << 22];
void push(int v){
if(lz[v]){
lz[v * 2 + 1] += lz[v];
lz[v * 2 + 2] += lz[v];
t[v * 2 + 1] += lz[v];
t[v * 2 + 2] += lz[v];
lz[v] = 0;
}
}
void init(int v, int l, int r){
if(l == r) t[v] = (1 << 30), lz[v] = 0;
else {
int m = (l + r) / 2;
init(v * 2 + 1, l, m);
init(v * 2 + 2, m + 1, r);
t[v] = 1 << 30, lz[v] = 0;
}
}
void range_add(int ql, int qr, int qv, int v, int l, int r){
if(qr < l || r < ql) return;
if(ql <= l && r <= qr) t[v] += qv, lz[v] += qv;
else {
push(v);
int m = (l + r) / 2;
range_add(ql, qr, qv, v * 2 + 1, l, m);
range_add(ql, qr, qv, v * 2 + 2, m + 1, r);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
}
int range_min(){
return t[0];
}
void point_update(int qi, int qv, int v, int l, int r){
if(l == r) t[v] = qv;
else {
push(v);
int m = (l + r) / 2;
if(qi <= m) point_update(qi, qv, v * 2 + 1, l, m);
else point_update(qi, qv, v * 2 + 2, m + 1, r);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
}
} ST;
int dp[4011][4011];
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
int n, d, t;
vector<range> R;
int ans = 0;
#ifdef RANGE
cin >> n >> d;
for(int i = 0; i < n; i++){
int l, r; cin >> l >> r; R.push_back({l, r});
}
#else
cin >> n >> d >> t;
for(int i = 0; i < n; i++){
cin >> a[i]; a[i] = max(0, t - a[i] + 1);
}
for(int i = 0; i < n; i++){
if(a[i] == 0) a[i] = -1;
else a[i] = min(n, i + a[i]), rm[a[i]].push_back(i);
}
priority_queue<int> pq1, pq2;
for(int i = 0; i < n; i++){
for(auto j : rm[i]) pq2.push(j);
while(pq1.size() && pq2.size() && pq1.top() == pq2.top()) pq1.pop(), pq2.pop();
if(a[i] == -1){
if(!pq1.empty()) R.push_back({pq1.top(), i - 1}), ans++;
}else{
pq1.push(i);
ans++;
}
}
#endif
for(auto [l, r] : R){
ps[r]++;
}
for(int i = 0; i < n - 1; i++){
ps[i + 1] += ps[i];
}
sort(R.begin(), R.end(), [](range a, range b){
return a.r < b.r;
});
fill(dp[0] + 1, dp[0] + n + 1, 1 << 30);
for(int i = 0; i <= d; i++){
int ri = 0; ST.init(0, 0, n);
for(int j = 0; j < n; j++){
ST.point_update(j, dp[i][j], 0, 0, n);
while(ri < R.size() && R[ri].r < j) ST.range_add(0, R[ri].l, 1, 0, 0, n), ri++;
dp[i + 1][j + 1] = ST.range_min();
}
}
int mx = ps[n - 1] - dp[d + 1][n];
cout << ans - mx << endl;
}
