#include <bits/stdc++.h>
#include "elephants.h"
#define DIM 150010
#define DIMBUCKET 400
using namespace std;
int n,lg,nr_buckets,l,q,cnt,poz,val;
int what_bucket[DIM],x[DIM];
pair <int,int> v[DIM],aux[DIM],dp[DIMBUCKET][DIMBUCKET*2];
vector <pair<int,int> > buckets[DIMBUCKET];
void update_bucket (int bucket){
int el = 0;
for (auto it : buckets[bucket])
aux[++el] = it;
int j = el+1;
for (int i=el;i;i--){
while (aux[j-1].first > aux[i].first + l)
j--;
if (j <= el){
dp[bucket][i].first = dp[bucket][j].first + 1;
dp[bucket][i].second = dp[bucket][j].second;
} else {
dp[bucket][i].first = 1;
dp[bucket][i].second = aux[i].first + l;
}
}
}
void build (int x[]){
lg = n / sqrt (n); /// lungime bucket
for (int i=1;i<=n;i++){
v[i].first = x[i-1];
v[i].second = i;
}
sort (v+1,v+n+1);
for (int i=1;i<=n;i++){
what_bucket[v[i].second] = i / lg;
if (i % lg)
what_bucket[v[i].second]++;
buckets[what_bucket[v[i].second]].push_back(v[i]);
}
nr_buckets = n / lg;
if (n % lg)
nr_buckets++;
for (int i=1;i<=nr_buckets;i++)
sort (buckets[i].begin(),buckets[i].end());
/// dp[bucket][i] - nr min de intervale cu care pot sa acopar toate punctele
/// din bucketul asta, incepand de la al i - lea, si care e cea mai din dreapta poz
/// pt care pot sa fac asta
for (int i=1;i<=nr_buckets;i++){
update_bucket(i);
}
}
int query (){
int poz = 1, sol = 0;
for (int i=1;i<=nr_buckets;i++){
sol += dp[i][poz].first;
int val = dp[i][poz].second;
/// trb sa vad care e noul poz in urmatorul bucket
/// daca sar peste mai multe bucketuri ce fac?
while (i < nr_buckets && buckets[i+1][ buckets[i+1].size() -1].first <= val)
i++;
if (i + 1 > nr_buckets)
break;
int st = 1, dr = buckets[i+1].size(), sol_poz = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[i+1][mid-1].first >= val){
sol_poz = mid;
dr = mid-1;
} else st = mid+1;
}
poz = sol_poz;
}
return sol;
}
void init (int _n, int _l, int v[]){
n = _n, l = _l;
build (v);
}
void sterge (int idx, int poz){
int i;
for (i=0;i<buckets[idx].size();i++)
if (buckets[idx][i] == v[poz])
break;
for (int j=i+1;j<buckets[idx].size();j++)
buckets[idx][j-1] = buckets[idx][j];
buckets[idx].pop_back();
}
void adauga (int idx, int poz){
int i;
for (i=0;i<buckets[idx].size();i++)
if (v[poz].first <= buckets[idx][i].first)
break;
buckets[idx].push_back(make_pair(0,0));
for (int j=buckets[idx].size()-1;j>i;j--)
buckets[idx][j] = buckets[idx][j-1];
buckets[idx][i] = v[poz];
}
int update (int poz, int val){
cnt++;
///if (cnt == lg) /// refac bucketurile
/// build();
poz++;
int idx = what_bucket[poz];
sterge (idx,poz);
//buckets[idx].erase(make_pair(v[poz].first,poz));
update_bucket (idx);
/// trb sa vad in ce bucket l as pune
v[poz].first = val;
int st = 1, dr = nr_buckets, sol = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[mid][0].first <= val){
sol = mid;
st = mid+1;
} else dr = mid-1;
}
what_bucket[poz] = sol;
adauga(sol,poz);
//buckets[sol].insert(v[poz]);
update_bucket(sol);
return query();
}
/*
int main (){
ifstream cin ("date.in");
ofstream cout ("date.out");
cin>>n>>l;
for (int i=0;i<n;i++)
cin>>x[i];
init(n,l,x);
cin>>q;
for (;q--;){
cin>>poz>>val;
cout<<update (poz,val)<<"\n";
}
return 0;
}
*/
