// ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
// ➡ @roadfromroi ⬅
// ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "queue"
#include "towers.h"
#define all(x) x.begin(), x.end()
using namespace std;
vector<int> h;
int dd;
struct node {
int lval;
int rval;
int cnt;
int lstenka;
int rstenka;
node() {}
node(int x) {
lval = rval = x;
cnt = 1;
lstenka = 0;
rstenka = 0;
}
void swapchik() {
swap(lval, rval);
swap(lstenka, rstenka);
}
};
node merge(node a, node b) {
bool swp = 0;
if (a.rval > b.lval) {
swp = 1;
a.swapchik();
b.swapchik();
swap(a, b);
}
node c = a;
if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
c.cnt = a.cnt + b.cnt;
c.rstenka = b.rstenka;
c.rval = b.rval;
if (swp)
c.swapchik();
return c;
} else {
c.cnt = a.cnt + b.cnt - 1;
if (b.cnt != 1) {
c.rstenka = b.rstenka;
c.rval = b.rval;
} else {
// cout << c.rstenka << ' ';
c.rstenka = max(c.rstenka, max(b.rstenka, max(b.lstenka, b.rval)));
// cout << c.rstenka << '\n';
}
if (swp)
c.swapchik();
return c;
}
}
struct kornihunka{
vector<int> elems;
node nd;
void push(int x) {
elems.push_back(x);
}
node get(int l, int r) {
r = min(r, (int)elems.size() - 1);
node nres(elems[l]);
for (int i = l + 1; i <= r; ++i) {
nres = merge(nres, node(elems[i]));
}
return nres;
}
void calc() {
nd = node(elems[0]);
for (int i = 1; i < elems.size(); ++i) {
nd = merge(nd, elems[i]);
}
}
node getnode() {
return nd;
}
};
int K = 337;
vector<kornihunka> vecnode;
int calcedd = 0;
void init(int n, vector<int> hh) {
h = hh;
vecnode.assign((n + K - 1) / K, {});
for (int i = 0; i < n; ++i) {
vecnode[i/K].push(h[i]);
}
}
int max_towers(int L, int R, int D) {
node res(2e9);
if (calcedd != D) {
if (calcedd != 0)
exit(1);
calcedd = D;
dd = D;
for (int i = 0; i < vecnode.size(); ++i) {
vecnode[i].calc();
}
}
if (L / K == R / K) {
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
res = merge(res, vecnode[L/K].get(L % K, R % K));
return res.cnt;
}
if (L % K != 0) {
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
res = merge(res, vecnode[L/K].get(L % K, K - 1));
L = L / K * K + K;
}
while (L + K <= R + 1) {
//cout << "TT " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
node res2 = vecnode[L/K].getnode();
//cout << "TT2 " << res2.lval << ' ' << res2.lstenka << ' ' << res2.cnt << '\n';
res = merge(res, vecnode[L/K].getnode());
//cout << "TT3 " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
L += K;
}
if (L <= R) {
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
res = merge(res, vecnode[L/K].get(L % K, R % K));
}
// cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
return res.cnt;
}
/*
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
init(n, a);
for (int i = 0; i < m; ++i) {
int q1, q2, q3;
cin >> q1 >> q2 >> q3;
cout << max_towers(q1,q2,q3) << '\n';
}
}*/
/*
7 1
10 20 60 40 50 30 70
0 6 17
*/
