#include "towers.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "stub.cpp"
#endif
const int N = 1e5 + 5;
int first, mount;
vector<int> a, l, r, res;
struct ST{
vector<int> tree;
int N;
ST(int N): N(N){
tree.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx){
tree[x] = v;
return;
}
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l){
return -(N << 2);
}
if(lx >= l && rx <= r){
return tree[x];
}
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get(int l, int r){
return get(l, r, 0, N, 1);
}
}Max(N), Min(N);
void init(int n, vector<int> H) {
first = 1;
a = H;
vector<int> pos_mnt;
for(int i=0;i<n;i++){
int is = 0;
if(!i || a[i] > a[i - 1]) is++;
if(i + 1 == n || a[i] > a[i + 1]) is++;
if(is == 2){
pos_mnt.push_back(i);
}
}
if((int)pos_mnt.size() == 1) mount = pos_mnt[0] + 1;
l.resize(n), r.resize(n);
ST Max(n), Min(n);
}
int max_towers(int l_, int r_, int d) {
if(mount){
int p = mount - 1;
if(l_ < p && p < r_ && a[l_] + d <= a[p] && a[r_] + d <= a[p]){
return 2;
}
return 1;
}
if(first){
int n = a.size();
vector<int> ss;
for(int i=0;i<n;i++){
while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
int l_ = 0, r_ = ss.size();
while(l_ < r_){
int m = (l_ + r_) >> 1;
if(a[ss[m]] >= a[i] + d) l_ = m + 1;
else r_ = m;
}
l[i] = 0;
if(l_) l[i] = ss[l_ - 1] + 1;
ss.push_back(i);
}
ss.clear();
for(int i=n-1;~i;i--){
while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
int l_ = 0, r_ = ss.size();
while(l_ < r_){
int m = (l_ + r_) >> 1;
if(a[ss[m]] >= a[i] + d) l_ = m + 1;
else r_ = m;
}
r[i] = n - 1;
if(l_) r[i] = ss[l_ - 1] - 1;
ss.push_back(i);
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
if(r[i] != r[j]) return r[i] < r[j];
if(l[i] != l[j]) return l[i] > l[j];
return a[i] < a[j];
});
int mxL = -1;
for(auto i : p){
if(l[i] <= mxL){
continue;
}
mxL = max(mxL, l[i]);
res.push_back(i);
}
for(int i=0;i<n;i++){
Min.set(i, -r[i]);
Max.set(i, l[i]);
}
first = 0;
}
int L = lower_bound(res.begin(), res.end(), l_) - res.begin();
int R = upper_bound(res.begin(), res.end(), r_) - res.begin() - 1;
if(L <= R){
int ans = R - L + 1;
if(l_ < l[res[L]]){
if(-Min.get(l_, l[res[L]] - 1) < l[res[L]]){
ans++;
}
}
if(r[res[R]] < r_){
if(r[res[R]] < Max.get(r[res[R]] + 1, r_)){
ans++;
}
}
return ans;
} else {
int mnR = -Min.get(l_, r_);
int mxL = Max.get(l_, r_);
if(mnR < mxL){
return 2;
}
return 1;
}
return 0;
}
