#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxN = 150000;
int n, l;
int positionsCameras[maxN];
int positions[maxN];
int posPerNumber[maxN];
void init(int N, int L, int X[])
{
n = N;
l = L;
for(int i = 0; i < N; ++i) {
positions[i] = X[i];
posPerNumber[i] = X[i];
}
}
int find(int rep){
int hi = n-1;
int lo = 0;
while(lo <= hi){
int mid = lo + (hi - lo)/2;
if(positions[mid] == rep) return mid;
if(positions[mid] < rep) lo = mid+1;
else hi = mid-1;
}
return 0;
}
int update(int i, int y)
{
int replace = posPerNumber[i];
posPerNumber[i] = y;
int pos = find(replace);
positions[pos] = y;
while(pos && positions[pos] < positions[pos-1]) {
swap(positions[pos], positions[pos-1]);
pos--;
}
while(pos < (n-1) && positions[pos] > positions[pos+1]) {
swap(positions[pos], positions[pos+1]);
pos++;
}
int numCameras = 0;
int right = -1;
for(int j = 0; j < n; ++j){
if(right < positions[j]){
numCameras++;
right = positions[j] + l;
}
}
return numCameras;
}
/*
int main(){
int N, L, Q, i, y;
cin >> N >> L;
int X[N];
for(int i = 0; i < N; ++i) cin >> X[i];
init(N, L, X);
cin >> Q;
while(Q--){
cin >> i >> y;
cout << update(i, y) << endl;
}
return 0;
}
*/
