#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long
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];
}
int arg_min(int v, int l, int r){
if(l == r) return l;
push(v);
int m = (l + r) / 2;
if(t[v * 2 + 1] == t[v]) return arg_min(v * 2 + 1, l, m);
else return arg_min(v * 2 + 2, m + 1, r);
}
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[N], c[N];
int n, d, t;
pair<int, int> calc(int pen, const vector<range>& R){
fill(dp + 1, dp + n + 1, 1 << 30);
int ri = 0; ST.init(0, 0, n);
for(int j = 0; j < n; j++){
ST.point_update(j, dp[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[j + 1] = ST.range_min() + pen; c[j + 1] = c[ST.arg_min(0, 0, n)] + 1;
}
return {dp[n] - pen * c[n], c[n] - 1};
}
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
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(0LL, 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;
});
int lo = 0, hi = n;
while(lo + 1 < hi){
int mid = (lo + hi) / 2;
pair<int, int> res = calc(mid, R);
if(res.second > d) lo = mid;
else hi = mid;
// printf("calc(%d) = {%d, %d}\n", mid, res.first, res.second);
}
pair<int, int> r1 = calc(lo, R);
pair<int, int> r2 = calc(hi, R);
int mn;
if(r1.second == r2.second){
assert(r1.second == d);
mn = r1.first;
}else{
mn = r1.first + (r2.first - r1.first) * (d - r1.second) / (r2.second - r1.second);
}
cout << ans - ps[n - 1] + mn << endl;
}
