#include <bits/stdc++.h>
#ifndef LOCAL
#include "elephants.h"
#endif // LOCAL
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
using namespace std;
const int MAX = 150000;
int magic = sqrt(MAX) + 10;
const int maxMagic = 500;
int N, L, x[MAX], tmp[MAX], nBlocks, countUpdates = 0;
vector<int> blocks[maxMagic];
pair<int, int> id[MAX];
int original[MAX];
vector<pair<int, int>> infoBlocks[MAX]; //[n_jumps, last_jump]
void buildBlock(int ib){
infoBlocks[ib].resize(sz(blocks[ib]));
for(int i = sz(blocks[ib]) - 1; i >= 0; --i){
if(i == sz(blocks[ib]) - 1){
infoBlocks[ib][i] = {1, blocks[ib][i] + L};
} else{
int l = i + 1, r = sz(blocks[ib]) - 1;
int n_jumps = 1, last_jump = blocks[ib][i] + L;
while(l <= r){
int mid = l + r >> 1;
if(blocks[ib][i] + L < blocks[ib][mid]){
n_jumps = infoBlocks[ib][mid].first + 1;
last_jump = infoBlocks[ib][mid].second;
r = mid - 1;
} else l = mid + 1;
}
infoBlocks[ib][i] = {n_jumps, last_jump};
}
}
}
int simulate(){
int total = 0, cur = -1;
for(int i = 0; i < nBlocks; ++i){
if(blocks[i].empty() || blocks[i].back() <= cur) {
continue; //over
}
int pos = upper_bound(all(blocks[i]), cur) - blocks[i].begin();
total += infoBlocks[i][pos].first;
cur = infoBlocks[i][pos].second;
}
return total;
}
void init(int _N, int _L, int _X[]){
N = _N;
L = _L;
for(int i = 0; i < N; ++i) x[i] = _X[i];
//tested for magic exactly sqrt(n)
magic = 500;
nBlocks = 0;
iota(original, original + N, 0);
for(int i = 0; i < N; i += magic, ++nBlocks){
int j = min(i + magic, N) - 1;
blocks[nBlocks] = vector<int>(x + i, x + j + 1);
buildBlock(nBlocks);
}
}
void debugBlock(int i){
cout << "block : " << i << '\n';
for(int x : blocks[i]) cout << x << ' ';
cout << '\n';
}
void debugAllBlock(){
for(int i = 0; i < nBlocks; ++i){
debugBlock(i);
}
}
void rebuild(){
copy(x, x + N, tmp);
sort(tmp, tmp + N);
nBlocks = 0;
for(int i = 0; i < N; i += magic, ++nBlocks){
int j = min(i + magic, N) - 1;
blocks[nBlocks] = vector<int>(tmp + i, tmp + j + 1);
buildBlock(nBlocks);
}
}
void remove(int x){
for(int i = 0; i < nBlocks; ++i){
if(blocks[i].empty()) continue;
if(!binary_search(all(blocks[i]), x)) continue;
blocks[i].erase(find(all(blocks[i]), x));
buildBlock(i);
return;
}
assert(false);
}
void insert(int x){
for(int i = 0; i < nBlocks; ++i){
if(blocks[i].empty()) continue;
if(blocks[i].back() > x){
int pos = upper_bound(all(blocks[i]), x) - blocks[i].begin();
blocks[i].insert(blocks[i].begin() + pos, x);
buildBlock(i);
return;
}
}
blocks[nBlocks - 1].push_back(x);
buildBlock(nBlocks - 1);
}
int update(int i, int y){
++countUpdates;
if(countUpdates == 2 * magic){
x[i] = y;
rebuild();
countUpdates = 0;
}
remove(x[i]);
x[i] = y;
insert(x[i]);
return simulate();
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int N, L;
cin >> N >> L;
int X[N];
for(int i = 0; i < N; ++i) cin >> X[i];
init(N, L, X);
int Q; cin >> Q;
while(Q--){
int i, y;
cin >> i >> y;
cout << update(i, y) << '\n';
}
return 0;
}
#endif // LOCAL
