#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 500005
const int inf = 1e15;
int n, a[N], m, dp[5001][5001], ans = inf, p[N];
int32_t main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= 5000; j++ ){
dp[i][j] = inf;
}
}
for(int i = 0; i <= m; i++) {
dp[0][i] = 1;
}
dp[0][0] = 0;
for(int i = 1; i <= n; i++) {
p[5001] = inf;
for(int j = 5000; j >= 0; j--) {
p[j] = min(p[j + 1], dp[i - 1][j]);
}
for(int j = 0; j <= 5000; j++) {
dp[i][j] = min(dp[i][j], p[max(j - m, 0ll)] + (j != a[i]));
}
}
for(int i = 0; i <= 5000; i++) {
ans = min(ans, dp[n][i]);
// cout << i << " " << dp[1][i] << endl;
}
cout << ans << '\n';
return 0;
}
