#include "elephants.h"
#include <bits/stdc++.h>
#define ar array
using namespace std;
const int INF = 1e9;
int l;
struct Koce{
vector<ar<int,2>> A;
vector<int> C, F;
int mn, mx;
Koce(){
}
void calc(){//In case you are new to the stream, calc is short for calculator btw
if(A.empty()){
mn = INF;
mx = -INF;
return;
}
C.clear(), F.clear();
int n = A.size();
C.resize(n), F.resize(n);
mn = A[0][0], mx = A.back()[0];
for(int i = n - 1; i >= 0;i--){
int j = upper_bound(A.begin(), A.end(), ar<int,2>{A[i][0] + l, INF}) - A.begin();
if(j == n)C[i] = 1, F[i] = A[i][0] + l;
else C[i] = C[j] + 1, F[i] = F[j];
}
}
ar<int,2> qry(int x){
if(A.empty())return {0, x};
int i = upper_bound(A.begin(), A.end(), ar<int,2>{x, INF}) - A.begin();
if(i == A.size())return {0, x};
return {C[i], F[i]};
}
};
vector<Koce> B;
int n;
const int b = 700;
vector<ar<int,2> > A;
vector<int> ind;
void bld(vector<ar<int,2>> A){
B.clear();
for(int i = 0;i < n;i++){
if(i % b == 0)B.push_back({});
B.back().A.push_back(A[i]);
ind[A[i][1]] = B.size() - 1;
}
for(auto &u: B)u.calc();
}
void rbld(){
vector<ar<int,2>> v;
int it = 0;
for(auto u: B){
for(auto x: u.A)v.push_back(x);
}
bld(v);
}
void init(int N, int L, int X[]){
n = N;
b = sqrt(n);
ind.resize(n);
l = L;
for(int i = 0;i < n;i++)A.push_back({X[i], i});
bld(A);
}
int cnt = 0;
int update(int i, int y){
int j = ind[i];
B[j].A.erase(find(B[j].A.begin(), B[j].A.end(), A[i]));
B[j].calc();
A[i][0] = y;
bool f = 0;
for(int x = 0; x < B.size();x++){
if(B[x].A.empty())continue;
if(y <= B[x].A.back()[0]){
f = 1;
B[x].A.insert(lower_bound(B[x].A.begin(), B[x].A.end(), A[i]), A[i]);
ind[i] = x;
B[x].calc();
break;
}
}
if(!f){
B.back().A.push_back(A[i]);
ind[i] = B.size() - 1;
B.back().calc();
}
cnt++;
if(cnt % b == 0)rbld();
int x = -1;
int ans = 0;
for(auto u: B){
auto [c, e] = u.qry(x);
ans += c;
x = e;
}
return ans;
}
