#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>
int n, m;
const int MN = 2e5 + 7, INF = 1e9+7;
int b[MN], a[MN], dp[MN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> b[i], a[i] = i*m-b[i];
dp[0] = -INF;
for(int i = 1; i <= n; i++) dp[i] = INF;
for(int i = 1; i <= n; i++) {
if(a[i] < 0) continue;
int l = upper_bound(dp+1, dp+1+n, a[i])-dp;
dp[l] = a[i];
}
int ans = 0;
for(int i = 1; i <= n; i++) if(dp[i] != INF) ans = i;
cout << n-ans << '\n';
}
# | 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... |