// source: https://oj.uz/problem/view/LMIO19_triusis #include <bits/stdc++.h> using namespace std; #define ll long long #define ar array int n, m, a[200001]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; a[0] = 1e9; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] = 1e9 - (a[i] - i * m); } vector<int> lis; for (int i = 1; i <= n; ++i) { if (a[i] >= 1e9) { auto it = upper_bound(lis.begin(), lis.end(), a[i]); if (it == lis.end()) lis.push_back(a[i]); else *it = a[i]; } } cout << n - lis.size(); return 0; }