#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef pair<int,int> pii;
#define pos first
#define ind second
int at[(int)2e5];
struct buck{
vector<pii> poz, inf;
};
const int S = 400;
int L, upd = 0;
buck bus[S];
int count(){
int ans = 0, last = -1;
for(int i = 0; i < S; i++){
int j = upper_bound(bus[i].poz.begin(), bus[i].poz.end(), pii(last, 2e9)) - bus[i].poz.begin();
if(j == bus[i].poz.size()) continue;
ans += bus[i].inf[j].first, last = bus[i].inf[j].second;
}
return ans;
}
void updateBuck(buck& b){
int last = b.poz.size();
b.inf.clear(), b.inf.resize(last);
for(int i = last-1; i >= 0; i--){
while(b.poz[last-1].pos - b.poz[i].pos > L) last--;
if(last == b.poz.size()) b.inf[i] = {1, b.poz[i].pos + L};
else b.inf[i] = {b.inf[last].first + 1, b.inf[last].second};
}
}
void beoszt(vector<pii>& els){
for(int i = 0, d = 0, id = 0; i < els.size(); i++){
if(++d == S) id++, d = 0;
bus[id].poz.push_back(els[i]);
at[els[i].ind] = id;
}
for(int i = 0; i < S; i++) updateBuck(bus[i]);
}
void remove(int from, int id){
vector<pii> uj;
for(pii& a : bus[from].poz)
if(a.second != id) uj.push_back(a);
bus[from].poz = uj;
updateBuck(bus[from]);
}
void insert(int id, pii ele){
vector<pii> uj;
at[ele.ind] = id;
for(pii& a : bus[id].poz){
if(ele.first < a.first) uj.push_back(ele), ele = {2e9,-1};
uj.push_back(a);
}
if(ele != pii(2e9, -1)) uj.push_back(ele);
bus[id].poz = uj;
updateBuck(bus[id]);
}
void init(int N, int l, int x[]){
L = l;
vector<pii> els(N);
for(int i = 0; i < N; i++) els[i] = {x[i], i};
beoszt(els);
}
int update(int i, int y){
remove(at[i], i);
int last = 0;
for(int i = 0; i < S; i++)
if(bus[i].poz.size() > 0 && y > bus[i].poz[0].pos) last = i;
insert(last, pii(y, i));
if(++upd%S == 0){
vector<pii> els;
for(int i = 0; i < S; i++){
for(pii& a : bus[i].poz) els.push_back(a);
bus[i].poz.clear();
}
beoszt(els);
}
return count();
}
/*int main(){
int N, L, M;
cin>>N>>L>>M;
int x[N];
for(int i = 0; i < N; i++) cin>>x[i];
init(N,L,x);
while(M--){
int i, y;
cin>>i>>y;
cout<<update(i, y)<<"\n";
}
}*/
