#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 5 "library2/utility/lwb.hpp"
template <class Container, class T> constexpr int lwb(const Container &c, const T &val) {
return static_cast<int>(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val)));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"
class ReversedRange {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
--itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr ReversedRange(const int f, const int l) noexcept
: first(l - 1), last(std::min(f, l) - 1) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr ReversedRange revrep(const int l, const int r) noexcept {
return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
return ReversedRange(0, n);
}
#line 3 "library2/utility/scan.hpp"
template <typename T = int> T scan() {
T ret;
std::cin >> ret;
return ret;
}
#line 5 "library2/utility/upb.hpp"
template <class Container, class T> constexpr int upb(const Container &c, const T &val) {
return static_cast<int>(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val)));
}
#line 9 "paper.cpp"
constexpr int NB = 1000, QB = 1000;
int N, L;
std::vector<int> X;
int blocks;
int count_query;
struct Warp {
int last;
int cost;
};
std::vector<int> limit;
std::vector<std::vector<std::pair<int, int>>> data;
std::vector<std::vector<Warp>> map;
std::vector<Warp> recalc(const std::vector<std::pair<int, int>> &x) {
const int n = len(x);
std::vector<Warp> ret(n);
int to = n;
for (const int i : revrep(n)) {
while (x[i].first + L < x[to - 1].first) {
--to;
}
if (to == n) {
ret[i] = {i, 0};
} else {
const auto &to_value = ret[to];
ret[i] = {to_value.last, to_value.cost + 1};
}
}
return ret;
}
void reset_all() {
std::vector<std::pair<int, int>> sorted_data;
auto collect = [&]() {
for (const int i : rep(blocks)) {
for (const auto &e : data[i]) {
sorted_data.push_back(e);
}
}
};
auto re_allocate = [&]() {
for (const int i : rep(blocks)) {
data[i].clear();
const int l = i * NB, r = std::min(len(sorted_data), (i + 1) * NB);
if (l >= r) {
break;
}
data[i].reserve(r - l);
for (const int j : rep(l, r)) {
data[i].push_back(sorted_data[j]);
}
map[i] = recalc(data[i]);
}
};
collect();
re_allocate();
auto calc_limit = [&]() {
for (const int i : rep(blocks)) {
limit[i] = data[i][0].first;
}
limit[0] = 0;
};
calc_limit();
}
void erase(const int value) {
const int block = upb(limit, value) - 1;
const auto itr =
std::lower_bound(data[block].begin(), data[block].end(), std::make_pair(value, 1));
if (itr->first == value) {
--data[block][itr - data[block].begin()].second;
if (data[block][itr - data[block].begin()].second == 0) {
data[block].erase(itr);
}
}
map[block] = recalc(data[block]);
}
void insert(const int value) {
const int block = upb(limit, value) - 1;
const auto itr =
std::lower_bound(data[block].begin(), data[block].end(), std::make_pair(value, 1));
if (itr->first == value) {
++data[block][itr - data[block].begin()].second;
} else {
data[block].insert(itr, {value, 1});
}
map[block] = recalc(data[block]);
}
void init(int n, int l, int x[]) {
N = n;
L = l;
count_query = 0;
std::copy(x, x + N, std::back_inserter(X));
blocks = (n + NB - 1) / NB;
limit.resize(blocks);
data.resize(blocks);
map.resize(blocks);
for (const int i : rep(N)) {
if (i == 0 or X[i] != X[i - 1]) {
data[0].push_back({X[i], 1});
} else {
++data[0].back().second;
}
}
reset_all();
}
int calc_answer() {
int ret = 0, now_block = -1, last = 0;
auto find_next = [&](const int value) {
while (true) {
++now_block;
if (now_block == blocks) {
break;
}
if (data[now_block].empty()) {
continue;
}
if (data[now_block].back().first < last) {
continue;
}
break;
}
if (now_block == blocks) {
return -1;
}
return lwb(data[now_block], std::make_pair(value, 1));
};
while (true) {
const int idx = find_next(last);
if (idx == -1) {
break;
}
ret += map[now_block][idx].cost;
++ret;
last = data[now_block][map[now_block][idx].last].first + L + 1;
if (now_block == blocks - 1) {
break;
}
}
return ret;
}
int update(int i, int y) {
++count_query;
if (count_query % QB == 0) {
reset_all();
}
erase(X[i]);
insert(y);
X[i] = y;
return calc_answer();
}
/*
int main() {
int n, l, m;
std::cin >> n >> l >> m;
int x[100];
for (const int i : rep(n)) {
std::cin >> x[i];
}
init(n, l, x);
while (m--) {
int i, y;
std::cin >> i >> y;
std::cout << update(i, y) << std::endl;
}
}
*/
