#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int k_N = 15e4 + 3;
struct Node;
typedef Node* pNode;
mt19937 mt(7);
struct Node{
int val, prior;
pNode l, r;
Node(){}
Node(int val){
this->val = val;
prior = mt();
l = r = nullptr;
}
};
void merge(pNode &t, pNode l, pNode r){
if(!l || !r)
return void(t = l ? l : r);
if(l->prior > r->prior)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
}
void split(pNode t, pNode &l, pNode &r, int val){
if(!t)
return void(l = r = nullptr);
if(val < t->val)
split(t->l, l, t->l, val), r = t;
else
split(t->r, t->r, r, val), l = t;
}
void insert(pNode &root, int val){
pNode l, r;
split(root, l, r, val);
merge(root, l, new Node(val));
merge(root, root, r);
}
void erase(pNode &root, int val){
if(root->val == val)
merge(root, root->l, root->r);
else
erase(val < root->val ? root->l : root->r, val);
}
int start, ans;
int n, l;
int *x;
pNode root = nullptr;
void solve(pNode t){
if(!t) return;
solve(t->l);
if(t->val - start > l){
start = t->val;
ans++;
}
solve(t->r);
}
void init(int N, int L, int X[]){
n = N;
l = L;
x = X;
for(int i = 0; i < n; ++i)
insert(root, x[i]);
}
int update(int idx, int y){
erase(root, x[idx]);
x[idx] = y;
insert(root, x[idx]);
start = -l - 1, ans = 0;
solve(root);
return ans;
}
/*
4 4 3
3 4 6 7
0 5 1
3 9 2
3 8 1
*/
