/** * Problem: Rabbit Carrot * Strategy: Transform condition a_j <= a_i + (j-i)*M into finding the * Longest Non-Increasing Subsequence of (a_i - i*M). * Complexity: O(N log N) */ #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // Optimize I/O operations for speed ios_base::sync_with_stdio(false); cin.tie(NULL); int n; long long m; // Read N and M if (!(cin >> n >> m)) return 0; // We don't need to store all raw inputs, we can process them on the fly // to build our filtered list for the subsequence calculation. vector<long long> valid_transformed_values; for (int i = 0; i < n; ++i) { long long a_i; cin >> a_i; // Formula: C_i = a_i - index * M // Note: The problem implies 1-based indexing logic for distance // (1st pole is distance 1 from start). long long c_val = a_i - (long long)(i + 1) * m; // Filter: The pole must be reachable from the start (height 0). // Condition: a_i <= index * M => a_i - index * M <= 0 if (c_val <= 0) { // To use the standard LIS (Longest Non-Decreasing) algorithm, // we negate the values. Finding LNIS of X is equivalent to // finding LNDS of -X. valid_transformed_values.push_back(-c_val); } } // If no poles are reachable/keepable, we must modify all of them. if (valid_transformed_values.empty()) { cout << n << endl; return 0; } // Calculate Longest Non-Decreasing Subsequence (LNDS) // We maintain a list 'tails' where tails[i] is the smallest ending element // of a non-decreasing subsequence of length i+1. vector<long long> tails; for (long long x : valid_transformed_values) { // upper_bound returns the first element strictly greater than x. // This allows us to extend a subsequence ending with a value <= x. auto it = upper_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { tails.push_back(x); } else { *it = x; } } // The length of 'tails' is the length of the longest subsequence we can keep. int max_kept_poles = tails.size(); // The result is total poles minus the ones we kept. cout << n - max_kept_poles << endl; return 0; }