#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void updateTree(int x, int L, int R, int ind, int newVal, vector<int> & seg) {
if (ind < L || ind > R) {
return;
} else if (L == R) {
seg[x] = newVal;
} else {
int mid = L + (R-L)/2;
updateTree(2*x, L, mid, ind, newVal, seg);
updateTree(2*x+1, mid+1, R, ind, newVal, seg);
seg[x] = max(seg[2*x], seg[2*x+1]);
}
}
int queryTree(int x, int L, int R, int startInd, int endInd, vector<int> & seg) {
if (startInd > R || endInd < L) {
return 0;
} else if (startInd <= L && endInd >= R) {
return seg[x];
} else {
int mid = L + (R-L)/2;
int leftAns = queryTree(2*x, L, mid, startInd, endInd, seg);
int rightAns = queryTree(2*x+1, mid+1, R, startInd, endInd, seg);
return max(leftAns, rightAns);
}
}
int lnds(vector<long long int> & L) {
// returns the length of the longest non-decreasing subsequence of L
int N = (int) L.size();
if (N == 0)
return 0;
vector<pair<long long int, int>> indL(N);
for (int i = 0; i < N; i++) {
indL[i] = make_pair(L[i], i);
}
sort(indL.begin(), indL.end());
vector<int> DP(N, 0);
vector<int> seg(4*N, 0);
updateTree(1, 0, N-1, indL[0].second, 1, seg);
for (int i = 1; i < N; i++) {
int curPos = indL[i].second;
int bestPrev = queryTree(1, 0, N-1, 0, curPos-1, seg);
updateTree(1, 0, N-1, curPos, bestPrev+1, seg);
}
return queryTree(1, 0, N-1, 0, N-1, seg);
}
int minChanges(vector<long long int> & heights, long long int M) {
int N = (int) heights.size();
vector<long long int> altered;
for (int i = 0; i < N; i++) {
long long int newH = M*((long long int) i+1) - heights[i];
if (newH >= 0) {
altered.push_back(newH);
}
}
return N - lnds(altered);
}
int main() {
int N;
long long int M;
cin >> N >> M;
vector<long long int> heights(N);
for (int i = 0; i < N; i++) {
cin >> heights[i];
}
cout << minChanges(heights, M) << '\n';
return 0;
}
