#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include "elephants.h"
/**
* Author: Nicholas Winschel
* Created: 06.06.2023 11:07:24
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
int n,l;
const int MAXN=150000;
const int BS=400,OBS=950;
int pos[MAXN],j[MAXN],h[MAXN],ord[MAXN],w[MAXN];
int buck[MAXN/BS + 5][3*OBS+1],s[MAXN/BS+5];
int cnt = 0;
int llt(int v, int x) {
if (!s[v] || pos[buck[v][0]] >= x) return -1;
int l = 0,r=s[v];
while (r-l>1) {
int m = (l+r)>>1;
if (pos[buck[v][m]] >= x) r=m;
else l=m;
}
return l;
}
void fixbuck(int i, int hint=0) {
if (s[i]>=2*OBS) cnt=2*BS;
// cerr << "fb: " << i << endl;
// for (int x =0; x < s[i]; x++) cerr << buck[i][x] << " ";
// cerr << endl;
if (!s[i] || hint >= s[i]) return;
j[buck[i][0]]=pos[buck[i][0]]-l,h[buck[i][0]]=1;
int lp = 0;
if (hint > 10) lp = max(lp, llt(i,pos[buck[i][hint]]-l));
for (int k = max(1,hint); k < s[i]; k++) {
while (lp < s[i]-1 && pos[buck[i][lp+1]]<pos[buck[i][k]]-l) lp++;
if (pos[buck[i][lp]] < pos[buck[i][k]]-l) {
// cerr << "test" << endl;
j[buck[i][k]]=j[buck[i][lp]];
h[buck[i][k]]=h[buck[i][lp]]+1;
} else {
j[buck[i][k]]=pos[buck[i][k]]-l;
h[buck[i][k]]=1;
}
}
}
void fixall() {
// cerr << "REALLOC" << endl;
int cur = 0;
for (int i = 0; i <= (n-1)/BS; i++) {
for (int x = 0; x < s[i]; x++) ord[cur++]=buck[i][x];
}
int c = 0;
for (int i = 0; i < n; i++) {
buck[i/BS][c++]=ord[i];
w[ord[i]]=i/BS;
if (i == n-1 || (i+1)/BS != i/BS) s[i/BS]=(c),c=0,fixbuck(i/BS);
}
}
void init(int N, int L, int X[])
{
n = N;
l = L;
memcpy(pos,X,N*sizeof(int));
for (int i = 0; i < N; i++) {
buck[i/BS][s[i/BS]++]=(i);
}
fixall();
}
int update(int i, int y)
{
// cerr << "mov: " << i << " " << y << endl;
if (cnt > BS) fixall(),cnt=0;
// buck[w[i]].erase(find(buck[w[i]].begin(),buck[w[i]].end(),i));
int ind = s[w[i]]-1;
for (int k = llt(w[i],pos[i])+1; k < s[w[i]]-1; k++) {
if (buck[w[i]][k]==i) {
ind=k;
break;
}
}
memmove(buck[w[i]] + ind, buck[w[i]] + ind + 1, (s[w[i]]-ind)*sizeof(int));
s[w[i]]--;
fixbuck(w[i],ind);
pos[i]=y;
w[i]=0;
for (int k = 0; k <= (n-1)/BS; k++) {
if (s[k] && pos[buck[k][0]] < pos[i]) w[i]=k;
}
ind = llt(w[i],pos[i])+1;
// buck[w[i]].insert(buck[w[i]].begin()+ind,i);
s[w[i]]++;
// cerr << "dbg2: " << ind << endl;
// for (int k = s[w[i]]-1; k > ind; k--) {
// // cerr << k << " " << buck[w[i]][k] << " " << buck[w[i]][k-1] << endl;
// buck[w[i]][k]=buck[w[i]][k-1];
// }
memmove(buck[w[i]]+ind+1,buck[w[i]]+ind,(s[w[i]]-ind)*sizeof(int));
buck[w[i]][ind]=i;
fixbuck(w[i],ind);
// for (int i = 0; i < n; i++) {
// cerr << "dbg: " << i << " " << pos[i] << " " << j[i] << " " << h[i] << endl;
// }
int cur = 2e9,ret=0;
for (int i = (n-1)/BS; i >= 0; i--) {
int ind = llt(i,cur);
if (ind >= 0) {
ind=buck[i][ind];
cur=j[ind],ret += h[ind];
// cerr << "jmp: " << cur << " " << ret << endl;
}
}
return ret;
}
