#include <bits/stdc++.h>
using namespace std;
using ld = long double;
ld eps = 0.000001d;
int n, d, t, v[2000005], k[2000005];
int bad;
struct copacel
{
ld val = 0;
int cate = 0;
};
copacel dp[2000005];
int sz[2000005];
vector<int> f[2000005];
ld c;
void dfs(int nod)
{
for (auto fiu : f[nod])
dfs(fiu);
copacel var1, var2;
var1.cate = 1;
var1.val = c;
for (auto fiu : f[nod])
{
if (dp[fiu].val < sz[fiu])
{
var1.cate += dp[fiu].cate;
var1.val += dp[fiu].val;
}
else
var1.val += sz[fiu];
}
if (f[nod].empty())
{
dp[nod] = var1;
return;
}
var2.val = var2.cate = 0;
ld mindif = 1e9;
for (auto fiu : f[nod])
mindif = min(mindif, dp[fiu].val - min(dp[fiu].val, (ld)sz[fiu]));
bool tkn = false;
for (auto fiu : f[nod])
{
if (!tkn and dp[fiu].val - min(dp[fiu].val, (ld)sz[fiu]) == mindif)
{
tkn = true;
var2.cate += dp[fiu].cate;
var2.val += dp[fiu].val;
}
else
{
if (dp[fiu].val < sz[fiu])
{
var2.cate += dp[fiu].cate;
var2.val += dp[fiu].val;
}
else
var2.val += sz[fiu];
}
}
if (var1.val < var2.val)
assert(false);
if (var1.val <= var2.val)
dp[nod] = var1;
else
dp[nod] = var2;
}
void solve(ld cost)
{
c = cost;
for (int i = 1; i <= n; i++)
dp[i].val = dp[i].cate = 0;
dfs(1);
}
void ufuf(int nod)
{
sz[nod] = 1;
for (auto fiu : f[nod])
{
ufuf(fiu);
sz[nod] += sz[fiu];
}
}
void build_tree()
{
vector<pair<int,int>> ranges;
vector<int> wow;
for (int i = 1; i <= n; i++)
{
wow.push_back(i);
int j = 0;
while (!wow.empty())
{
int jcur = wow.back();
if (v[jcur] + i - jcur > t)
wow.pop_back();
else
{
j = jcur;
break;
}
}
if (j == i)
bad++;
else if (j != 0)
ranges.push_back({j, i - 1});
}
if (ranges.empty())
{
n = 0;
return;
}
ranges.push_back({1, n});
sort(ranges.begin(), ranges.end(), [](pair<int,int> A, pair<int,int> B){
if (A.first != B.first)
return A.first < B.first;
return A.second > B.second;
});
n = ranges.size();
stack<int> stk;
stk.push(1);
for (int i = 1; i < n; i++)
{
while (ranges[stk.top() - 1].second < ranges[i].first)
stk.pop();
f[stk.top()].push_back(i + 1);
stk.push(i + 1);
}
ufuf(1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> d >> t;
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++)
k[i] = v[i] - i;
build_tree();
if (n - 1 <= d)
{
cout << bad;
return 0;
}
ld st = n, pas = (ld)(1 << 20);
while (pas >= eps)
{
if (st - pas >= 1)
{
solve(st - pas);
if (dp[1].cate <= d)
st -= pas;
}
pas /= 2.0d;
}
solve(st);
ld ans = dp[1].val - (ld)d * st;
int aa = ans;
if (ans - (ld)aa >= 0.5d)
aa++;
cout << aa + bad;
return 0;
}
/**
yeah so aliens pe fata
pentru i, imi fac un interval de tipul: "daca pun aici un gate nu o sa se mai revolte i"
in fine, astea au structura de arbore din fericire, deci dupa ce imi fac arborele si aliens, e doar un dp[nod][0/1]
**/
