#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
int T=300,B=150000/T+3;
int a,b,c,d,e,i,j,ii,jj,zx,xc,L,lef,rig,mid,k[150009],f[150009],C,D,cnt,II,JJ,pas;
vector <int> v[150009],vv;
vector <pair <int, int> > dp[150009];
void REBL(int q){
int lef,rig,mid,h=q,hh;
dp[h].resize(v[h].size());
if(v[h].size()==0) return;
for(hh=v[h].size()-1; hh>=0; hh--){
lef=hh;rig=v[h].size();
while(lef+1<rig){
mid=((lef+rig)>>1);
if(v[h][mid]>v[h][hh]+L){
rig=mid;
}else{
lef=mid;
}
}
if(rig==v[h].size()){
dp[h][hh]={1,v[h][hh]+L};
}else{
dp[h][hh]=dp[h][rig];dp[h][hh].first++;
}
}
}
void REDO(){
int lef,rig,mid;
int h=0,hh=0,qw=0;vv.clear();
for(h=1; h<=B; h++){
for(hh=0; hh<v[h].size(); hh++){
vv.push_back(v[h][hh]);
}
v[h].clear();
}
qw=0;
for(h=0; h<vv.size(); h++){
if(h%T==0) qw++;
v[qw].push_back(vv[h]);
}
for(h=1; h<=B; h++){
k[h]=k[h-1];
if(v[h].size()==0) continue;
k[h]=v[h][v[h].size()-1];
REBL(h);
}
k[B]=1000000003;
}
void init(int NN, int LL, int XX[]){
a=NN;L=LL;
for(i=1; i<=a; i++){
v[1].push_back(XX[i-1]);
f[i]=XX[i-1];
}
REDO();
}
int fnd(int q){
int lef,rig,mid;
lef=0;rig=B+1;
while(lef+1<rig){
mid=((lef+rig)>>1);
if(k[mid]>=q){
rig=mid;
}else{
lef=mid;
}
}
return rig;
}
int fndbl(int q, int w){
int lef,rig,mid;
lef=-1;rig=v[q].size();
while(lef+1<rig){
mid=((lef+rig)>>1);
if(v[q][mid]>=w){
rig=mid;
}else{
lef=mid;
}
}
return rig;
}
int update(int Ii, int Yy){
int h,hh;
Ii++;
i=Ii;D=Yy;C=f[i];cnt++;
ii=fnd(C);e=0;
if(k[ii]==C){
if(v[ii].size()==0||v[ii][v[ii].size()-1]!=C){
ii++;II=0;e=1;
}
}
if(e==0){
II=fndbl(ii,C);
}
v[ii].erase(v[ii].begin()+II);
jj=fnd(D);
JJ=fndbl(jj,D);
v[jj].insert(v[jj].begin()+JJ,D);
REBL(ii);REBL(jj);
if(cnt%T==0) REDO();
f[i]=D;
II=-2;pas=0;
for(h=1; h<=B; h++){
if(v[h].size()==0) continue;
c=fndbl(h,II+1);
if(c==v[h].size()){
continue;
}
pas+=dp[h][c].first;II=dp[h][c].second;
}
return pas;
}
