#include <bits/stdc++.h> using namespace std; vector<vector<int>> sons; vector<pair<int, int>> subtree; //subtree[i].first max depth of the subtree rooted in i; subtree[i].second is the farthest node from the root in teh subtree rooted in i void dfs(int nodoAtt){ subtree[nodoAtt]={1, nodoAtt}; for(int son : sons[nodoAtt]){ dfs(son); if(subtree[son].first+1>subtree[nodoAtt].first){ subtree[nodoAtt].first=subtree[son].first+1; subtree[nodoAtt].second=subtree[son].second; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N, D, S; cin >>N >>D >>S; vector<int> T(N); for(int i=0; i<N; i++) cin >>T[i]; sons.resize(N); subtree.resize(N); vector<bool> isInfectable(N, true); int alwaysSafe=0; int indMax=-1; for(int i=0; i<N; i++){ if(T[i]<=S){ indMax=max(indMax, i+S-T[i]); }else if(i>indMax){ isInfectable[i]=false; alwaysSafe++; } } vector<int> parent(N, -1); //-1 -> Non appartiene a nessun albero, se fosse radice sarebbe parent di sé stesso queue<int> roots; stack<int> safe; for(int i=N-1; i>=0; i--){ if(T[i]<=S){ indMax=i+S-T[i]; while(!safe.empty() && safe.top()<=indMax){ safe.pop(); } }else if(isInfectable[i]){ if(!safe.empty()){ parent[i]=safe.top(); sons[safe.top()].push_back(i); }else{ parent[i]=i; roots.push(i); } safe.push(i); } } priority_queue<pair<int, int>> pq; while(!roots.empty()){ dfs(roots.front()); pq.push({subtree[roots.front()].first, roots.front()}); roots.pop(); } int totSaved=alwaysSafe; for(int i=0; i<D && !pq.empty(); i++){ int rootAtt=pq.top().second; totSaved+=pq.top().first; pq.pop(); int nodoAtt=subtree[rootAtt].second, lastNodo; while(nodoAtt!=rootAtt){ lastNodo=nodoAtt; nodoAtt=parent[nodoAtt]; for(int son : sons[nodoAtt]){ if(son==lastNodo) continue; pq.push({subtree[son].first, son}); } } } cout <<N-totSaved; }