#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
#define FOR(i , a , b) for(int i = a ; i <= b; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int a[maxn];
ll b[maxn] ,c[maxn];
int main(){
FAST;
int n;
ll M;
cin >> n >> M;
FOR(i , 1 , n) cin >> a[i];
int c_size = 0;
FOR(i , 1 , n){
if(M * i >= a[i]){
c[i] = M * i - 1ll*a[i];
++c_size;
}
}
FOR(i , 1 , c_size) b[i] = 2e9;
int ans = 0;
FOR(i , 1 , c_size){
int k = upper_bound(b + 1, b + c_size + 1, c[i]) - b;
b[k] = c[i];
ans = max(ans , k);
}
cout << n - ans;
}
# | 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... |