#include <iostream>
using namespace std;
const int N = 5005;
int dp[N][N], a[N], Ans = N;
int main(){
int n, m, M = 0;
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i], M = max(M, a[i]);
for (int i=0;i<=n;i++){
for (int j=0;j<=M;j++)
dp[i][j] = n;
}
dp[0][0] = 0;
for (int i=1;i<=n+1;i++){
// print(n, M, i-1);
for (int j=M-1;j>=0;j--)
dp[i-1][j] = min(dp[i-1][j], dp[i-1][j+1]);
for (int j=0;j<=M;j++){
dp[i][j] = dp[i-1][max(0, j - m)] + (a[i] != j);
if (i == n)
Ans = min(Ans, dp[i][j]);
}
}
cout<<Ans<<'\n';
}
