#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a (n, 0);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
set<pair<int, int>> s;
s.insert({0, 0});
int w = n;
for (int i = 0; i < n; i++) {
int x = a[i]-m*(i+1);
auto y = s.lower_bound({x, 0});
if (y == s.end()) {
continue;
}
auto z = *y;
pair<int, int> b = {x, z.second+1};
w = min(w, n-b.second);
if (y != s.begin()) {
s.erase(--y);
}
if (z.first == x) {
s.erase(z);
}
s.insert(b);
}
cout << w << '\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... |