#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxa = 5000 + 1;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector <int> nums(n+1);
for (int i = 1; i <= n; i++) {
cin >> nums[i];
}
if (m == 0) {
int ans = 0;
for (int i = 1; i <= n; i++) {
if (nums[i] != 0)
ans++;
}
cout << ans << '\n';
return 0;
}
int prev = 0, curr = 1;
vector <vector <int>> dp(2, vector <int> (maxa));
vector <vector <int>> mn_vals(2, vector <int> (maxa));
bool flag = false;
for (int i = maxa-1; i >= 0; i--) {
if (flag || (i <= m && i == nums[1])) {
dp[1][i] = 0;
mn_vals[1][i] = 0;
flag = true;
} else if (i <= m) {
mn_vals[1][i] = 1;
dp[1][i] = 1;
} else {
mn_vals[1][i] = 1e9;
dp[1][i] = 1e9;
}
}
swap(prev, curr);
for (int i = 2; i <= n; i++) {
for (int j = 0; j < maxa; j++) {
int a = mn_vals[prev][max(0, j - m)];
dp[curr][j] = a;
if (nums[i] != j) {
dp[curr][j]++;
}
}
for (int j = maxa-1; j >= 0; j--) {
mn_vals[curr][j] = dp[curr][j];
if (j+1 < maxa)
mn_vals[curr][j] = min(mn_vals[curr][j+1], mn_vals[curr][j]);
}
swap(prev, curr);
}
int ans = 1e9;
for (int i = 0; i < maxa; i++)
ans = min(ans, dp[prev][i]);
cout << ans << '\n';
}
