#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define pb push_back #define ff first #define ss second #define ii pair<int, int> #define vi vector<int> #define vii vector<pair<int, int>> #define yes cout << "YES\n" #define no cout << "NO\n" #define mii map<int, int> #define rep(i, a, b) for (int i = a; i <= b; i++) #define all(a, len) (a) + 1, (a) + len + 1 #define vall(a) (a).begin(), a.end() #define _READ(name) freopen(name, "r", stdin) #define _WRITE(name) freopen(name, "w", stdout) const int INF = 4e18; const int MOD = 1e9 + 7; int n, m; const int mx = 2e5 + 3; int a[mx]; void TheEminemShow() { cin >> n >> m; rep(i, 1, n) cin >> a[i]; } void Recovery() { /* chon phan tu toi da KHONG sua i1 < i2 < ... < ik - a[i[j]] <= m*i[j] <=> 0 <= m*i[j] - a[i[j]] - a[i[j+1]] <= a[i[j]] + m*(i[j+1] - i[j]) <=> a[i[j+1]] <= a[i[j]] + m*i[j+1] - m*i[j] <=> a[i[j+1]] - m*i[j+1] <= a[i[j]] - m*i[j] <=> m*i[j+1] - a[i[j+1]] >= m*i[j] - a[i[j]] */ vi vec, dp; rep(i, 1, n) { if (m*i >= a[i]) vec.pb(m*i - a[i]); } for (auto it: vec) { int j = upper_bound(dp.begin(), dp.end(), it) - dp.begin(); if (j == dp.size()) dp.pb(it); else dp[j] = it; } cout << n - dp.size(); } void Kamikaze() { } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int TEST = 1; // cin >> TEST; while (TEST--) { TheEminemShow(); Recovery(); Kamikaze(); } return 0; }