#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for (int i=l; i<=r; i++)
void solve() {
int n, m; cin >> n >> m;
vector<int> dp(n+1, 1e9);
// dp[0] = 0;
// aj <= ai + M*(j-i)
// M*j - aj >= M*i - ai
// bj >= bi
int res = 0;
FOR(i, 1, n) {
int a; cin >> a;
int b = m*i-a;
if (b < 0) continue;
auto it = lower_bound(dp.begin(), dp.end(), b);
*it = b;
res = max(res, int (it - dp.begin()));
}
cout << n-res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |