#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
using namespace std;

const int MAXN = 150005, B = 400, MAXB = 805;

int n, m, len;
int L[MAXB], R[MAXB], bl[MAXN], a[MAXN], b[MAXN];
int C, cnt[MAXB][MAXB], en[MAXB][MAXB], val[MAXB][MAXB], sz[MAXB];
map<int, int> mp;

int getbl(int x) {
	return lower_bound(R, R + C + 1, x) - R;
}

void rebuild(int x) {
	for (int i = sz[x]; i; i--) {
		int p = lower_bound(val[x] + 1, val[x] + sz[x] + 1, val[x][i] + len + 1) - val[x];
		if (p == sz[x] + 1)
			en[x][i] = val[x][i] + len, cnt[x][i] = 1;
		else
			en[x][i] = en[x][p], cnt[x][i] = 1 + cnt[x][p];
	}
}

void rebuild() {
	for (int i = 1; i <= n; i++)
		b[i] = a[i];
	sort(b + 1, b + n + 1);
	m = unique(b + 1, b + n + 1) - b - 1;
	b[m + 1] = 1e9 + 5, C = (m - 1) / B + 1;
	for (int i = 0; i <= C; i++)
		sz[i] = 0;
	for (int i = 1; i <= m; i++)
		bl[i] = (i - 1) / B + 1, R[bl[i]] = b[i + 1] - 1, val[bl[i]][++sz[bl[i]]] = b[i];
	for (int i = m; i; i--)
		L[bl[i]] = b[i];
	L[0] = 0, R[0] = b[1] - 1;
	for (int i = 0; i <= C; i++)
		rebuild(i);
}

void init(int N, int Len, int *x) {
	n = N, len = Len;
	for (int i = 1; i <= n; i++)
		a[i] = x[i - 1], mp[a[i]]++;
	rebuild();
}

int tmp[MAXB], c = 0, f = 0;

void del(int x, int v) {
	c = f = 0;
	for (int i = 1; i <= sz[x]; i++) {
		if (val[x][i] == v && !f)
			f = 1;
		else
			tmp[++c] = val[x][i];
	}
	sz[x] = c;
	for (int i = 1; i <= c; i++)
		val[x][i] = tmp[i];
	rebuild(x);
}

void insert(int x, int v) {
	c = f = 0;
	for (int i = 1; i <= sz[x]; i++) {
		if (val[x][i] > v && !f)
			f = 1, tmp[++c] = v;
		tmp[++c] = val[x][i];
	}
	if (!f)
		tmp[++c] = v;
	sz[x] = c;
	for (int i = 1; i <= c; i++)
		val[x][i] = tmp[i];
	rebuild(x);
	if (sz[x] > 2 * B)
		rebuild();
}

int update(int x, int y) {
	x++, mp[a[x]]--;
	if (!mp[a[x]])
		del(getbl(a[x]), a[x]);
	a[x] = y;
	if (!mp[y])
		insert(getbl(y), y);
	mp[y]++;
	int lst = -1, ans = 0;
	for (int i = 0; i <= C; i++) {
		int p = lower_bound(val[i] + 1, val[i] + sz[i] + 1, lst + 1) - val[i];
		if (p == sz[i] + 1)
			continue;
		ans += cnt[i][p], lst = en[i][p];
	}
	return ans;
}