#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define test(v) \ for (auto &x : (v)) { \ cout << x << " "; \ } \ cout << "\n"; #define test2d(v) \ for (int i = 0; i < (int)v.size(); i++) { \ for (int j = 0; j < (int)v[i].size(); j++) { \ cout << v[i][j] << " "; \ } \ cout << '\n'; \ } #define pb push_back vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count()); int hashp = uniform_int_distribution<int>(10, 1e9)(rng); int hashm1 = 1e9+7; int hashm2 = 1e9+9; int MOD = 1e9+7; int MV = 1e18; void solve(){ int n, m; cin >> n >> m; vector<int> dp; for(int i = 1; i <= n; i++){ int a; cin >> a; if(i*m >= a){ int cur = i*m - a; int pos = upper_bound(dp.begin(), dp.end(), cur) - dp.begin(); if(pos == dp.size()) dp.pb(cur); else dp[pos] = cur; } } cout << n - dp.size(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* freopen("cowjog.in", "r", stdin); freopen("cowjog.out", "w", stdout); */ solve(); return 0; }