#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 100005
struct tree {
struct node {
node(int l, int r) : l(l), r(r) {}
int l = 0; int r = 0; int v = 0;
node* lc = nullptr;
node* rc = nullptr;
};
vector<node*> rt;
vector<int> nums;
tree() {
nums.push_back(numeric_limits<int>::min());
rt.push_back(build(0, mx));
}
void upd(int idx, int val, int v) {
//cout << "index: " << idx << "," << "value: " << val << "," << "time: " << v << endl;
nums.push_back(v); // v = time
rt.push_back(upd2(rt.back(), idx, val));
}
node* build(int l, int r) {
node* rt = new node(l, r);
if (l == r) return rt;
int m = (l + r) / 2;
rt->lc = build(l, m);
rt->rc = build(m + 1, r);
return rt;
}
node* upd2(node* rt, int idx, int v) {
//return the root
if (rt->l > idx || rt->r < idx) return rt;
node* tr = new node(*rt); //copy?
if (tr->l == tr->r) {
tr->v = v;
return tr;
}
tr->lc = upd2(tr->lc, idx, v);
tr->rc = upd2(tr->rc, idx, v);
tr->v = tr->lc->v + tr->rc->v;
return tr;
}
array<int, 3> query(int l, int r, int t) {
node* vv = rt.at((upper_bound(nums.begin(), nums.end(), t) - nums.begin())-1);
return { queryL(vv, l), queryR(vv, r), queryS(vv, l, r)};
}
int queryS(node* rt, int l, int r) {
if (rt->l > r || rt->r < l)return 0;
if (rt->l >= l && rt->r <= r) return rt->v;
return queryS(rt->lc, l, r) + queryS(rt->rc, l, r);
}
int queryL(node* rt, int l) { //query left most with index >= l and value >= v
if (rt->r < l) return -1;
if (!rt->v) return -1;
if (rt->l == rt->r) return rt->l;
int res = queryL(rt->lc, l);
return res == -1 ? queryL(rt->rc, l) : res;
}
int queryR(node* rt, int r) { //query right most with index <= r
if (rt->l > r) return -1;
if (!rt->v) return -1;
if (rt->l == rt->r) return rt->l;
int res = queryR(rt->rc, r);
return res == -1 ? queryR(rt->lc, r) : res;
}
} open, close;
vector<int> h;
//struct mintree { //ehh should be sparse tablebut wtv
// struct node {
// node(int l, int r) : l(l), r(r) {};
// int v = numeric_limits<int>::max();
// int l, r;
// node *lc = 0, *rc = 0;
// };
// node* rt;
// mintree() {
// rt = build(0, mx);
// }
// node* build(int l, int r) {
// node* rt = new node(l, r);
// if (l == r) return rt;
// int m = (l + r) / 2;
// rt->lc = build(l, m);
// rt->rc = build(m + 1, r);
// return rt;
// }
// void upd(int i, int v) {
// upd2(rt, i, v);
// }
// void upd2(node* rt, int i, int v) {
// if (i < rt->l || i > rt->r) return;
// if (rt->l == rt->r) {
// rt->v = v;
// return;
// }
// upd2(rt->lc, i, v); upd2(rt->rc, i, v);
// rt->v = min(rt->lc->v, rt->rc->v);
// }
// int query(int l, int r) {
// return query2(rt, l, r);
// }
// int query2(node* rt, int l, int r) {
// if (l > rt->r || r < rt->l) return numeric_limits<int>::max();
// if (rt->l >= l && rt->r <= r) return rt->v;
// return min(query2(rt->lc, l, r), query2(rt->rc, l, r));
// }
//} ac2;
#define ll int
struct difftree { //what the fk am i doing
struct node {
node(int l, int r) : l(l), r(r) {};
ll mn = std::numeric_limits<int>::max()/2;
ll ma = std::numeric_limits<int>::min()/2;
ll incdif = 0, decdif = 0;
int l, r;
node* lc = 0, * rc = 0;
};
node* rt = 0;
difftree() {
rt = build(0, mx);
//cout << rt->l << "," << rt->r << endl;
}
node* build(int l, int r) {
node* rt = new node(l, r);
if (l == r) return rt;
int m = (l + r) / 2;
rt->lc = build(l, m);
rt->rc = build(m + 1, r);
return rt;
}
void upd(int i, int v) {
upd2(rt, i, v);
}
void upd2(node* rt, int i, int v) {
if (i < rt->l || i > rt->r) return;
if (rt->l == rt->r) {
rt->mn = rt->ma = v;
return;
}
upd2(rt->lc, i, v); upd2(rt->rc, i, v);
rt->mn = min(rt->lc->mn, rt->rc->mn);
rt->ma = max(rt->lc->ma, rt->rc->ma);
rt->incdif = max(max(rt->lc->incdif, rt->rc->incdif), rt->rc->ma - rt->lc->mn);
rt->decdif = max(max(rt->lc->decdif, rt->rc->decdif), rt->lc->ma - rt->rc->mn);
}
int incdif(int l, int r) {
node amogus = query2(rt, l, r);
int tmp = amogus.incdif;
return tmp;
}
int decdif(int l, int r) {
node amogus = query2(rt, l, r);
int tmp = amogus.decdif;
return tmp;
}
node query2(node* rt, int l, int r) {
//cout << "gonna kms" << endl;
//cout << l << "," << rt->l << "," << r << "," << rt->r << endl;
if (l > rt->r || r < rt->l) return node(-1,-1);
if (rt->l >= l && rt->r <= r) return *rt;
node owo(-1, -1);
node lc = query2(rt->lc, l, r);
node rc = query2(rt->rc, l, r);
owo.mn = min(lc.mn, rc.mn);
owo.ma = max(lc.ma, rc.ma);
owo.incdif = max(max(lc.incdif, rc.incdif), rc.ma - lc.mn);
owo.decdif = max(max(lc.decdif, rc.decdif), lc.ma - rc.mn);
return owo;
}
} diff;
//
//struct dsu {
// vector<int> p, r;
// dsu() {
// p.resize(mx, -1);
// r.resize(mx, 0);
// }
// int par(int x) {
// return p.at(x) == -1 ? x : p.at(x) = par(p.at(x));
// }
// void merge(int a, int b) {
// a = par(a), b = par(b);
// if (a == b) return;
// //attaching b to a, so r.at(a) must be bigger
// if (r.at(a) < r.at(b)) swap(a, b);
// if (r.at(a) == r.at(b)) r.at(a)++;
// p.at(b) = a;
// }
//};
void init(int N, vector<int> H) {
h = H;
h.insert(h.begin(), numeric_limits<int>::max()); N++;
set<int> ranges;
for (int i = 0; i < N; i++)
ranges.insert(i);
vector<int> mn = h;
vector<bool> exists(N, 1);
set<pair<int, int>> q;
for (int i = 0; i < N; i++) {
//ac2.upd(i, h.at(i));
diff.upd(i, h.at(i));
open.upd(i, 1, numeric_limits<int>::min());
close.upd(i+1, 1, numeric_limits<int>::min());
int v = numeric_limits<int>::max();
if (i) v = min(v, h.at(i) - mn.at(i));
if (i < N - 1)v = min(v, h.at(i + 1) - mn.at(i));
q.insert({ v, i });
}
int time = numeric_limits<int>::min();
while (q.size()) {
auto [a, b] = *q.begin();
time = max(time, a);
q.erase(q.begin());
if (!exists.at(b)) continue;
auto x = ranges.find(b);
if (b && h.at(b) - mn.at(b) <= a) {
//deletus
auto x2 = x; x2--;
if (exists.at(*x2)) {
exists.at(*x) = 0;
open.upd(*x, 0, time);
auto x3 = x; x3++;
if (x3 == ranges.end()) close.upd(N, 0, time);
else close.upd(*x3, 0, time);
continue;
}
int tmp = mn.at(b);
exists.at(*x) = 0;
exists.at(*x2) = 1;
open.upd(*x, 0, time);
open.upd(*x2, 1, time);
ranges.erase(x--);
mn.at(*x) = min(mn.at(*x), tmp);
}
else {
auto x2 = x; x2++;
//assert(x2 != ranges.end()); //troll
if (x2 == ranges.end()) {
continue;
}
if (exists.at(*x2)) {
open.upd(*x, 0, time);
close.upd(*x2, 0, time);
exists.at(*x) = 0;
continue;
}
if (x2 != ranges.end() && h.at(*x2) - mn.at(*x) <= a) {
mn.at(*x) = min(mn.at(*x), mn.at(*x2));
exists.at(*x2) = 0;
close.upd(*x2, 0, time);
auto x3 = x2; x3++;
if(x3 != ranges.end())close.upd(*x3, 1, time);
else close.upd(N, 1, time);
ranges.erase(x2);
}
else {
break;
}
}
//x is result
b = *x; int v = numeric_limits<int>::max();
if (b) v = min(v, h.at(b) - mn.at(b));
x++;
if (x != ranges.end()) v = min(v, h.at(*x) - mn.at(b));
q.insert({ v, b });
//yeahhhhhhh......
}
h = H;
}
int max_towers(int L, int R, int D) {
L++, R++; D--;
//this is so sus
auto [a, b, c] = open.query(L, R, D);
auto [e, f, g] = close.query(L, R, D);
//auto .at(x, y, z) = open.query(0, 7, numeric_limits<int>::min());
//cout << x << "," << y << "," << z << endl;
//cout << c << "," << g << endl;
if (c && g && e <= a) {
g--;
}
if (c && g && b >= f) {
c--;
}
if (c == 0 || g == 0) {
//AMONGUS
int l = L, r = R, m = 0;
int inc = 0, dec = 0;
while (l < r) {
m = (l + r) / 2;
inc = diff.incdif(L, m);
dec = diff.decdif(m, R);
//cout <<L<<","<<R<<","<<m << "," << inc << "," << dec << endl;
if (min(inc, dec) >= D+1) break;
if (max(inc, dec) < D + 1)break;
if (inc < dec)
l = m + 1;
else
r = m - 1;
}
//cout << "." << endl;
if (min(inc, dec) >= D+1) {
return 2;
}
else {
return 1;
}
}
//cout << a << "," << b << "," << c << endl;
//cout << e << "," << f << "," << g << endl;
//assert(a != -1);
//assert(b != -1);
//assert(e != -1);
//assert(f != -1);
//assert(c == g);
//cout << diff.incdif(L, a) << "," << L << "," << a << endl;
if (diff.incdif(L, a) >= D+1) c++;
if (diff.decdif(f, R) >= D+1) c++;
return c;
}
//
//int main() {
// int N, Q;
// assert(2 == scanf("%d %d", &N, &Q));
// std::vector<int> H(N);
// for (int i = 0; i < N; ++i) {
// assert(1 == scanf("%d", &H.at(i)));
// }
// init(N, H);
//
// for (int i = 0; i < Q; ++i) {
// int L, R, D;
// assert(3 == scanf("%d %d %d", &L, &R, &D));
// printf("%d\n", max_towers(L, R, D));
// }
// return 0;
//}
