#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
* LIOI 2019 - Trusis (Quyon)
* Vaqt murakkabligi: O(N log N)
*/
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
long long M;
if (!(cin >> N >> M)) return 0;
vector<long long> b;
for (int i = 1; i <= N; i++) {
long long a_i;
cin >> a_i;
// Quyon i-chi ustunga chiqa olishi uchun a_i <= i * M bo'lishi shart
if (a_i <= i * M) {
// b_i = i * M - a_i shartini o'zgartirmasdan saqlash mumkin bo'lganlar uchun qo'llaymiz
b.push_back(i * M - a_i);
}
}
// b massivida eng uzun kamaymaydigan qism ketma-ketlikni (LIS) topamiz
// Buning uchun O(N log N) algoritmidan foydalanamiz
vector<long long> lis;
for (long long x : b) {
auto it = upper_bound(lis.begin(), lis.end(), x);
if (it == lis.end()) {
lis.push_back(x);
} else {
*it = x;
}
}
// O'zgartirilishi kerak bo'lgan ustunlar soni = Jami - Saqlab qolinganlar
cout << N - (int)lis.size() << endl;
return 0;
}
