#include <bits/stdc++.h> #include <queue> using namespace std; #define ff endl #define lf "\n" #define _ << ' ' << #define all(x) begin(x),end(x) #define rall(x) rbegin(x),rend(x) #define infor(str, ...) do { fprintf(stderr, str, ##__VA_ARGS__); } while(0) #define infof(str, ...) do { fprintf(stderr, str"\n", ##__VA_ARGS__); } while(0) #ifndef DEBUG #undef infor #undef infof #define infor(str, ...) #define infof(str, ...) #endif using ll = long long; constexpr int LOG = 20; constexpr int MOD = 1e9+7; constexpr int MAXN = 1e5+7; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, D, K; cin >> N >> D >> K; vector<int> V(N); for(auto &x: V) cin >> x; vector<bool> P(N); int last = V[0], y = 0; for(int i = 1; i < N; ++i) { last = min(last + 1, V[i]); if(last <= K) y++; P[i] = (V[i] > K) != (last > K); } vector<int> F(N, -1); vector<vector<int>> adj(N); int r = 0; stack<array<int, 2>> s; s.push({-1, 0}); for(int i = 0; i < N; ++i) { if(P[i]) { while(s.size() > 1) { auto [j, rr] = s.top(); r = max(r, rr); if(i < r) break; s.pop(); F[j] = i; adj[i].push_back(j); } s.top()[1] = r; s.push({i, 0}); r = 0; } r = max(r, K - V[i] - i); } vector<int> d(N), f(N); auto dfs = [&](int v, auto &&dfs) -> void { d[v] = 0; f[v] = v; for(auto u: adj[v]) { dfs(u, dfs); if(d[v] >= d[u] + 1) continue; f[v] = f[u]; d[v] = d[u] + 1; } }; for(int i = 0; i < N; ++i) if(F[i] < 0) dfs(i, dfs); int ans = 0; priority_queue<array<int, 2>> q; for(int i = 0; i < N; ++i) if(F[i] < 0 && P[i]) q.push({d[i], i}); while(D--) { auto [x, i] = q.top(); q.pop(); ans += x; int v = f[i]; while(F[v] >= 0) { for(auto u: adj[v]) q.push({d[u], u}); v = F[v]; } } cout << y - ans << lf; }