/////////////////////////////////////////////// EPILOGUE ///////////////////////////////////////////////
// Author: @mohitdmak
// NOTE: code inside this fxn at end of template or after importing it
// void start(){ }
/////////////////////////////////////////////// END ///////////////////////////////////////////////
/////////////////////////////////////////////// GCC AND LIBS OPTIMIZATIONS ///////////////////////////////////////////////
#pragma GCC optimize("Ofast")
// #pragma GCC optimize("O0") // for something related to double precision optimization? (checkout)
// // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") // below removed "avx2" as SPOJ gives runtime error due to "SIGILL" for some reason
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,fma")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h" // going for precompiling headers for stl lib collection (#include <bits/stdc++.h>) through make job
using namespace std;
#ifndef ONLINE_JUDGE
#include <sys/resource.h>
#endif
/////////////////////////////////////////////// END ///////////////////////////////////////////////
/////////////////////////////////////////////// DEBUGGING FUNCTIONS ///////////////////////////////////////////////
// COUTing pairs
template <typename S, typename V>
ostream& operator<<(ostream& os, const pair<S, V>& ppair) {
os << "P:{" << ppair.first << "," << ppair.second << "}";
return os;
}
// COUTing sets (only 1Ds at the moment)
// template <typename S, class Iterator>
template <typename S, typename V>
ostream& operator<<(ostream& os, const set<S, V>& sset) {
os << "Set:[";
for (auto element : sset) { os << element << ","; }
os << "]";
return os;
}
// COUTing multisets (only 1Ds at the moment)
// template <typename T, typename S, typename V>
template <typename S, typename V>
ostream& operator<<(ostream& os, const multiset<S, V>& mset) {
os << "MSet:[";
for (auto element : mset) { os << element << ","; }
os << "]";
return os;
}
// COUTing vectors (only 1Ds at the moment)
template <typename S>
ostream& operator<<(ostream& os, const vector<S>& vvector) {
os << "V:[";
for (auto element : vvector) { os << element << ","; }
os << "]";
return os;
}
// COUTing deques
template <typename S>
ostream& operator<<(ostream& os, const deque<S>& ddeque) {
os << "Dq:[";
for (auto element : ddeque) { os << element << ","; }
os << "]";
return os;
}
// COUTing maps (only 1Ds at the moment)
template <typename S, typename V>
ostream& operator<<(ostream& os, const map<S, V>& mmap) {
os << "M:[";
for (auto element : mmap) { os << element.first << ":" << element.second << ","; }
os << "]";
return os;
}
// COUTing unordered maps (only 1Ds at the moment)
template <typename S, typename V>
ostream& operator<<(ostream& os, const unordered_map<S, V>& mmap) {
os << "uM:[";
for (auto element : mmap) { os << element.first << ":" << element.second << ","; }
os << "]";
return os;
}
// COUTing queues
template <typename T>
ostream& operator<<(ostream& os, queue<T> mq) {
os << "Q:[";
while (mq.size()){
T element = mq.front(); mq.pop();
os << element << ",";
}
os << "]";
return os;
}
// COUTing stacks
template <typename T>
ostream& operator<<(ostream& os, stack<T> mq) {
os << "S:[";
while (mq.size()){
T element = mq.top(); mq.pop();
os << element << ",";
}
os << "]";
return os;
}
// COUTing priority_queue
// template <typename T, typename S, typename V>
template <typename T, typename S, typename V>
ostream& operator<<(ostream& os, const priority_queue<T, S, V>& mpq) {
priority_queue<T, S, V> copyPQ(mpq);
os << "PQ:[";
while (copyPQ.size()) { os << copyPQ.top() << ","; copyPQ.pop(); }
os << "]";
return os;
}
/* debugging error variables and values */
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); cerr << "\nDEBUG: "; err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << "; ";
err(++it, args...);
}
vector<string> X_splitStr(string s, vector<string> delims){
string curr = s;
int curr_pos = 0;
vector<string> tokenized;
while(curr.size()){
int delim_size = 0;
for (string delim: delims){
int curr_size = (int)curr.size();
curr = curr.substr(0, curr.find(delim));
if ((int)curr.size() != curr_size) delim_size = delim.size();
}
curr_pos += (int)curr.size() + delim_size;
if (curr.size()) tokenized.push_back(curr);
curr = s.substr(curr_pos);
}
return tokenized;
}
/////////////////////////////////////////////// END ///////////////////////////////////////////////
/////////////////////////////////////////////// SHORTHANDS / DEFINITIONS ///////////////////////////////////////////////
#define _n_ << "\n" // newline
#define __ << " " << // space
const int BS = 21; // no of bits to print in X_BS
const int MOD = 1e9 + 7;
typedef long long ll;
vector<ll> FACTORIALS;
/////////////////////////////////////////////// END ///////////////////////////////////////////////
/////////////////////////////////////////////// UTILITY FUNCTIONS ///////////////////////////////////////////////
// Matrix ops like power (bin exponentiation), etc <==> (Template is just to support int / long long)
template<class T> struct X_Mat{
vector<vector<T>> mat; int r, c, mod; // mod is used during mul ops
X_Mat(): r(0), c(0) {} // default constructor (don't initialize vector 'o vector)
X_Mat(int r_, int c_, int mod_ = 0, int val_ = 0): r(r_), c(c_), mod(mod_) { mat = vector<vector<T>>(r_, vector<T>(c, val_)); }
X_Mat operator*(const X_Mat &mat2){ // mul op -> O(N^3) where |mat| ~ N x N
assert(c == mat2.r); // m1 x m2 -> can only cross if of form [axb]X[bxc]
X_Mat res(r, mat2.c, mod); // response matrix (carry forth mod info, initialize with 0s)
for (int i = 0; i < r; i++) for (int j = 0; j < mat2.c; j++) for (int k = 0; k < c; k++){ // matrix mul
if (!mod) res.mat[i][j] += mat[i][k] * mat2.mat[k][j];
else res.mat[i][j] = (res.mat[i][j] + (1ll * mat[i][k] * mat2.mat[k][j] % mod)) % mod;
}
return res;
}
X_Mat operator*=(const X_Mat &mat2){ return *this = (*this) * mat2; } // simply assign res of mul op
// O(N^3.log(p)) -> friend function to use externally, using bin exponentiation on matrices
friend X_Mat X_MatPower(X_Mat m, ll p){
assert(m.r == m.c); // only square matrices can be raised to powers
X_Mat res(m.r, m.c, m.mod); // response matrix (in bin exponentiation we gotta ensure identity matrix to mul with mat)
for (int i = 0; i < m.r; i++) res.mat[i][i] = 1;
for (; p; p >>= 1){ // bin exponentiation
if (p & 1) res *= m;
m *= m;
}
return res;
}
};
// Double-Ended Priority Queue
class X_DoublePQ{
public:
multiset<int> pq;
// O(1) returns size of priority queue
int size() { return (int)pq.size(); }
// O(logn) inserts into priority queue
void insert(int x) { pq.insert(x); }
// O(1) gets min el
int min() { return *pq.begin(); }
// O(1) gets max el
int max() { return *pq.rbegin(); }
// O(logn) deletes min el
void deleteMin() {
if (!pq.size()) return;
pq.erase(pq.begin());
}
// O(logn) deletes max el
void deleteMax() {
if (!pq.size()) return;
auto itr = pq.end(); itr--;
pq.erase(itr);
}
};
// DSU
class X_DSU{
public:
vector<ll> id;
vector<ll> size;
void make_set(ll n){
id = vector<ll> (n);
size = vector<ll> (n, 1);
for (ll i = 0; i < n; i++) id[i] = i;
}
void clear_set(){
for (ll i = 0; i < (ll)id.size(); i++) { id[i] = i; size[i] = 1; }
}
ll find_set(ll v){
if (v == id[v]) return v;
return id[v] = find_set(id[v]);
}
ll total_set(){
ll total = 0;
for (ll i = 0; i < (ll)id.size(); i++) total += (i == id[i]) ? 1 : 0;
return total;
}
void union_set(ll u, ll v){
ll uID = find_set(u), vID = find_set(v);
if (uID != vID){
if (size[uID] > size[vID]){
id[vID] = uID;
size[uID] += size[vID];
} else {
id[uID] = vID;
size[vID] += size[uID];
}
}
}
};
// Get bitset print of input
bitset<BS> X_bs(ll ip){ return bitset<BS>(ip); }
bitset<BS> X_bs(int ip){ return bitset<BS>(ip); }
// Returns random in [a,b]
int X_rand(int a, int b) { return a + rand() % (b - a + 1); }
// Euclid's gcd algorithm
// $$ TIME: O(log(min(a, b)))
ll X_gcd (ll a, ll b){
while (b) {
a %= b;
swap(a, b);
}
return a;
}
// Euclid's extended algorithm, find x,y s.t ax + by = gcd(a,b)
// $$ TIME: O(log(min(a, b)))
ll X_gcd_extended(ll a, ll b, ll& x, ll& y){
x = 1, y = 0;
ll x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1) {
ll q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}
// Computes the total no of solutions (x,y) for `ax + by = c`, with x1<=x<=x2 and y1<=y<=y2, returns -1 if ~infinite sols
// $$ TIME: O(log(min(a,b)))
ll X_diophantine_total_sols(ll a, ll b, ll c, pair<ll, ll> xRange = {0, LLONG_MAX}, pair<ll, ll> yRange = {0, LLONG_MAX}){
// checking for any infinity type bound
bool infInvolved = (xRange.second == LLONG_MAX || yRange.second == LLONG_MAX || xRange.first == LLONG_MIN || yRange.first == LLONG_MIN);
// PRUNE: Edge Cases
if (!a && !b && c) return 0;
else if (!a && !b && !c) return ((infInvolved) ? -1 : (xRange.second - xRange.first + 1) * (yRange.second - yRange.first + 1));
else if (!a || !b){
if (!a){
if (!(c % b) && yRange.first <= (c / b) && (c / b) <= yRange.second) return ((!infInvolved) ? xRange.second - xRange.first + 1 : -1);
else return 0;
} else {
if (!(c % a) && xRange.first <= (c / a) && (c / a) <= xRange.second) return ((!infInvolved) ? yRange.second - yRange.first + 1 : -1);
else return 0;
}
}
// Getting a single solution
ll x, y, g;
g = X_gcd_extended((ll)a, (ll)b, x, y);
if (c % g) return 0;
ll x0 = x * (c / g), y0 = y * (c / g);
double ag = a / g, bg = b / g;
// Getting range of k for x,y and combined range kZ
pair<ll, ll> kX, kY, kZ;
if (kX.first == LLONG_MIN) kX.first = LLONG_MIN;
else kX.first = (x0 >= xRange.first) ? -floor((double)(x0 - xRange.first) / abs(bg)) : ceil((double)(xRange.first - x0) / abs(bg));
if (kY.first == LLONG_MIN) kY.first = LLONG_MIN;
else kY.first = (y0 >= yRange.first) ? -floor((double)(y0 - yRange.first) / abs(ag)) : ceil((double)(yRange.first - y0) / abs(ag));
if (xRange.second == LLONG_MAX) kX.second = LLONG_MAX;
else kX.second = (x0 >= xRange.second) ? -ceil((double)(x0 - xRange.second) / abs(bg)) : floor((double)(xRange.second - x0) / abs(bg));
if (yRange.second == LLONG_MAX) kY.second = LLONG_MAX;
else kY.second = (y0 >= yRange.second) ? -ceil((double)(y0 - yRange.second) / abs(ag)) : floor((double)(yRange.second - y0) / abs(ag));
if (bg < 0) kX = {-kX.second, -kX.first};
if (ag < 0) kY = {-kY.second, -kY.first};
kZ = {-kY.second, -kY.first};
// Prune and return
if ((kY.first > kY.second) || (kX.first > kX.second)) return 0;
kZ = {max(kZ.first, kX.first), min(kZ.second, kX.second)};
return ((kZ.first <= kZ.second) ? kZ.second - kZ.first + 1 : 0);
}
// Computes and returns all primes upto n as a bool array;
// possible optimizations - see for only odd nos (memory & time halved, done if `ignoreEven`) / see segmented sieve
// $$ TIME: O(n log(log n)); MEMORY [IMP]: O(n)
vector<bool> X_sieve(ll n, bool ignoreEven = false){
vector<bool> is_prime(n+1, true);
is_prime[2] = true;
is_prime[0] = is_prime[1] = false;
for (int i = 2 + (int)ignoreEven; i * i <= n; i += 1 + (int)ignoreEven) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i * (1 + (int)ignoreEven)) is_prime[j] = false;
}
}
return is_prime;
}
// Computes only the COUNT of primes upto n; Better than X_sieve on memory - O(sqrt(n)); if `store` is true, primes are stored in `allPrimes`
// $$ TIME: O(n log(log sqrt(n))); MEMORY [IMP]: O(sqrt(n))
ll X_sieve_segmented_count(ll n, vector<ll> &allPrimes, bool store = false) {
const ll S = 10000; // block/segment size (generally 1e4 - 1e5)
vector<ll> primes;
ll nsqrt = sqrt(n);
vector<char> is_prime(nsqrt + 2, true);
for (ll i = 2; i <= nsqrt; i++) { // store primes till sqrt(n)
if (is_prime[i]) {
primes.push_back(i);
for (ll j = i * i; j <= nsqrt; j += i) {
is_prime[j] = false;
}
}
}
ll result = 0; // total count of primes
vector<char> block(S);
for (ll k = 0; k * S <= n; k++) { // mark primes for each block
fill(block.begin(), block.end(), true);
ll start = k * S;
for (ll p : primes) {
ll start_idx = (start + p - 1) / p;
ll j = max(start_idx, p) * p - start;
for (; j < S; j += p)
block[j] = false;
}
if (k == 0) block[0] = block[1] = false;
for (ll i = 0; i < S && start + i <= n; i++) {
if (block[i]){
result++;
if (store) allPrimes.push_back(start + i); // actual prime no is start+i, store if told
}
}
}
return result;
}
// Computes and stores bool of array of primes in range [L, R]; Uses segmented Seive
// $$ TIME: O(n log(log sqrt(n))); MEMORY [IMP]: O(sqrt(n)) [n = R - L]
vector<bool> X_sieve_segmented_all(ll L, ll R) {
// generate all primes up to sqrt(R)
ll lim = sqrt(R);
vector<char> mark(lim + 1, false);
vector<ll> primes;
for (ll i = 2; i <= lim; ++i) {
if (!mark[i]) {
primes.emplace_back(i);
for (ll j = i * i; j <= lim; j += i){
mark[j] = true;
}
}
}
vector<bool> isPrime(R - L + 1, true);
for (ll i : primes){
for (ll j = max(i * i, (L + i - 1) / i * i); j <= R; j += i){
isPrime[j - L] = false;
}
}
if (L == 1) isPrime[0] = false;
return isPrime;
}
// get prime factors, returns vector of pairs of ll, where first == prime factor, second == it's power
//
// $$ TIME: O(sqrt(N))
vector<pair<ll, ll>> prime_factors_sqrt(ll N){
ll prime = 2, n = N;
vector<pair<ll, ll>> res(0);
while (prime * prime <= n){
if (N % prime == 0) {
ll count = 0;
while (N % prime == 0) { N /= prime; count++; }
res.push_back({prime, count});
}
prime++;
}
return res;
}
// get prime factors, returns vector of pairs of ll, where first == prime factor, second == it's power
//
// $$ TIME: O(log(N)) for composite N; O(N) for prime N
vector<pair<ll, ll>> prime_factors_sieve(ll N){
ll prime = 2;
vector<pair<ll, ll>> res(0);
while (N > 1){
if (N % prime == 0) {
ll count = 0;
while (N % prime == 0) { N /= prime; count++; }
res.push_back({prime, count});
}
prime++;
}
return res;
}
// Euler's Totient Function - gives no of nos less than x which are coprime with n
//
// $$ TIME: O(sqrt(N) * log(N)) for composite N; O(N) for prime N
ll phi(ll N){
ll prime = 2, n = N;
float res = n;
while (prime * prime <= n){
if (N % prime == 0){
while (N % prime == 0){ N /= prime; }
res *= (1.0 - (1.0 / (float)prime)); // or res -= res / prime
}
prime++;
}
if (N > 1) { res *= (1.0 - (1.0 / (float)N)); } // or res -= res/N
return (ll)res;
}
// Computes factorials from last highest previously precomputed factorial to currently asked and all in between.
// $$ TIME: Depends on last precomputed factorial and current number (O(N))
ll X_factorial_mod(ll n, ll m){
if (n+1>(ll)FACTORIALS.size() && FACTORIALS.size()!=0){
ll p = FACTORIALS[FACTORIALS.size()-1];
//FACTORIALS.push_back(p);
ll i=FACTORIALS.size();
for(; i<=n; i++) {
p = (p * i) % m;
FACTORIALS.push_back(p);
}
return p;
}
else if (FACTORIALS.size()==0){
ll p = 1;
FACTORIALS.push_back(p);
ll i=FACTORIALS.size();
for(; i<=n; i++) {
p = (p * i) % m;
FACTORIALS.push_back(p);
}
return p;
}
else {
return FACTORIALS[n];
}
}
// Computes a^b efficiently
// $$ TIME: O(log(b))
ll X_power(ll a, ll b){
if (b == 0) return 1;
ll res = X_power(a, b/2);
return (b % 2) ? res * res * a : res * res;
}
// Computes a^b efficiently while keeping answer mod m
// $$ TIME: O(log(b))
ll X_power_mod(ll a, ll b, ll m = LLONG_MAX){
if (b == 0){ return 1; }
ll res = X_power_mod(a, b/2, m) % m;
res = (res * res) % m;
if (b % 2){
return (res * a) % m;
} else {
return res;
}
}
// Computes mod inverse of a wrt m, i.e a^-1 mod m; using euclid's extended algorithm; CONDITION: a,m to be coprime
// $$ TIME: O(log(min(a, m))) [NOTE: returns -1 if inverse doesn't exist!]
ll X_mod_inverse(ll a, ll m){
ll x, y, res;
ll g = X_gcd_extended(a, m, x, y);
if (g != 1){
cout << "Inverse doesn't exist! A and M are not coprime!";
res = -1;
} else {
res = (x % m + m) % m; // m is added to handle negative x
}
return res;
}
// uses fermat's little theorum for computing mod inverse of a wrt m; states that a^-1 mod m = a^(m-2) mod m; CONDITION: m to be prime
// $$ TIME: O(log(m))
ll X_mod_inverse_fermat(ll a, ll m){
// ll g = X_gcd(a, m);
// if (g != 1){
// cout << "Inverse doesn't exist! A and M are not coprime!";
// return -1;
// } else {
// return X_power_mod(a, m - 2, m);
// }
return X_power_mod(a, m - 2, m);
}
// Computes (a / b) mod m; mod inverse of b needs to exist with m (i.e gcd(b,m)=1), else -1 is returned
// $$ TIME: O(log(b))
ll X_mod_division(ll a, ll b, ll m){
ll inverse = X_mod_inverse(b, m);
if (inverse == -1) return -1;
ll modDiv = ((a % m) * inverse) % m;
if (modDiv < 0) modDiv += m;
return modDiv;
}
// computes nCr while keeping answer mod m; by computing n!, and mod inverses of r!, (n-1)!
// $$ TIME: O(N) : O(N) for precomputing factorials till n; 2*O(log(m)) for computing 2 mod inverses
ll nCr_mod(ll n, ll r, ll m) {
ll p = ((X_factorial_mod(n, m) * X_mod_inverse(FACTORIALS[r], m)) % m * X_mod_inverse(FACTORIALS[n-r], m)) % m;
return p;
}
/////////////////////////////////////////////// END ///////////////////////////////////////////////
/////////////////////////////////////////////// DRIVER CODE ///////////////////////////////////////////////
#ifndef ONLINE_JUDGE
clock_t tStart = clock();
#endif
void start(); // cpp programs
void generate(int argc, char* argv[]); // generator for stress testing
void computeRuntime(){
#ifndef ONLINE_JUDGE
fprintf(stderr, "\n>>> [@mohitdmak]: !OJ_mode: Runtime: %.6fs <<<\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
#endif
}
int main(int argc, char* argv[]){
ios_base::sync_with_stdio(false);
cin.tie(NULL) ; cout.tie(NULL);
// cout.precision(numeric_limits<double>::max_digits10);
#ifndef ONLINE_JUDGE
rlimit R;
getrlimit(RLIMIT_STACK, &R);
R.rlim_cur = R.rlim_max;
setrlimit(RLIMIT_STACK, &R);
#endif
#ifndef MOHITDMAK_GENERATOR_MODE // flagged within generator
start();
#else
generate(argc, argv);
#endif
#ifndef ONLINE_JUDGE
#ifndef MOHITDMAK_STRESS_TESTING_MODE // flagged within counter brutes
computeRuntime();
#endif
#endif
return (0) ;
}
/////////////////////////////////////////////// END ///////////////////////////////////////////////
int n, m, h[200001];
void solve(){
// error(n, m);
// for (int i = 0; i <= n; i++) error(i, h[i]);
auto cmp = [](int i, int j){ return h[i] - m * i > h[j] - m * j; };
multiset<int, decltype(cmp)> dp(cmp);
for (int i = 1; i <= n; i++){
if (h[i] > m * i) continue;
auto itr = dp.upper_bound(i);
// error(i, h[i], dp, itr==dp.end());
if (itr == dp.end()) dp.insert(i);
else dp.erase(itr), dp.insert(i);
}
cout << n - dp.size();
}
void start(){
cin >> n >> m; int i = 0; while (i++ < n) cin >> h[i];
solve();
}
