#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
struct PersSeg {
vector<int> tree;
vector<int> le;
vector<int> ri;
vector<int> roots;
int n;
int _init(int s, int e) {
if (s==e) {
int p =tree.size();
tree.push_back(0);
le.push_back(-1);
ri.push_back(-1);
return p;
}
int m = (s+e)/2;
int l = _init(s,m);
int r = _init(m+1,e);
int p =tree.size();
tree.push_back(0);
le.push_back(l);
ri.push_back(r);
return p;
}
void init(int _n) {
n = _n;
if (n==0) return;
roots.push_back(_init(0,n-1));
}
int upd(int idx, int val, int s, int e, int ori) {
if (idx<s||e<idx) {
return ori;
}
if (s==e) {
int p = tree.size();
tree.push_back(tree[ori]+val);
le.push_back(-1);
ri.push_back(-1);
return p;
}
int m =(s+e)/2;
int l = upd(idx,val,s,m,le[ori]);
int r = upd(idx,val,m+1,e,ri[ori]);
int p = tree.size();
tree.push_back(tree[ori]+val);
le.push_back(l);
ri.push_back(r);
return p;
}
void upd(int idx, int val) {
if (n==0) return;
int root = upd(idx, val, 0, n-1, roots.back());
roots.push_back(root);
}
int getv(int S, int E, int s, int e, int ori) {
if (e<S||E<s) return 0;
if (S<=s&&e<=E) return tree[ori];
int m = (s+e)/2;
return getv(S,E,s,m,le[ori])+getv(S,E,m+1,e,ri[ori]);
}
int getv(int S, int E, int ori) {
return getv(S,E,0,n-1,ori);
}
};
struct Seg {
vector<pii> tree[270000]; // v, r
vector<int> comp[270000]; // r
vector<int> rootnum[270000];
PersSeg per[270000];
const int key = 131072;
void upd(int idx, pii p) {
idx += key;
while(idx) {
tree[idx].push_back(p);
idx/=2;
}
}
void calc() {
for (int i=1;i<key*2;i++) {
// printf("%d!\n",i);
sort(tree[i].begin(),tree[i].end());
for (pii &p : tree[i]) {
comp[i].push_back(p.second);
}
sort(comp[i].begin(),comp[i].end());
comp[i].erase(unique(comp[i].begin(),comp[i].end()),comp[i].end());
per[i].init(tree[i].size());
rootnum[i].assign(tree[i].size(),0);
for (int j=(int)tree[i].size()-1;j>=0;j--) {
int r = lower_bound(comp[i].begin(),comp[i].end(),tree[i][j].second)-comp[i].begin();
per[i].upd(r,1);
rootnum[i][j] = per[i].roots.back();
}
}
}
int _getv(int i, int d, int rs, int re) {
int t =lower_bound(tree[i].begin(),tree[i].end(),pii(d,-1))-tree[i].begin();
// for (pii &p : tree[i]) {
// printf("(%d, %d) ",p.first,p.second);
// }
// printf("%d!\n",d);
if (t==tree[i].size()) return 0;
rs = lower_bound(comp[i].begin(),comp[i].end(),rs)-comp[i].begin();
re = upper_bound(comp[i].begin(),comp[i].end(),re)-comp[i].begin()-1;
return per[i].getv(rs,re,rootnum[i][t]);
}
int getv(int s, int e, int d, int rs, int re) {
s += key; e += key;
int ans = 0;
while(s<=e) {
if (s&1) {
ans += _getv(s,d,rs,re);
}
if (~e&1) {
ans += _getv(e,d,rs,re);
}
s = (s+1)/2;
e = (e-1)/2;
}
return ans;
}
} itr, itl;
struct Idxtree {
int tree[270000];
const int key = 131072;
void init() {
memset(tree,0x3f,sizeof(tree));
}
void upd(int idx, int val) {
idx += key;
while(idx) {
tree[idx] = min(tree[idx],val);
idx/=2;
}
}
int getv(int s, int e) {
s += key;
e += key;
int ans = INF;
while(s<=e) {
if (s&1) ans = min(ans,tree[s]);
if (~e&1) ans = min(ans,tree[e]);
s = (s+1)/2;
e = (e-1)/2;
}
return ans;
}
} ith;
struct MIdxtree {
int tree[270000];
const int key = 131072;
void init() {
memset(tree,0,sizeof(tree));
}
void upd(int idx, int val) {
idx += key;
while(idx) {
tree[idx] = max(tree[idx],val);
idx/=2;
}
}
int getv(int s, int e) {
s += key;
e += key;
int ans = 0;
while(s<=e) {
if (s&1) ans = max(ans,tree[s]);
if (~e&1) ans = max(ans,tree[e]);
s = (s+1)/2;
e = (e-1)/2;
}
return ans;
}
} ithm;
int N;
vector<int> H;
int pr[100100], pl[100100];
int l[100100], r[100100];
map<int,int> loc;
void init(int _N, vector<int> _H) {
N = _N;
H = _H;
ith.init();
ithm.init();
for (int i=0;i<N;i++) {
ith.upd(i,H[i]);
ithm.upd(i,H[i]);
loc[H[i]] = i;
}
vector<int> st;
for (int i=0;i<=N;i++) {
int h = (i==N?INF:H[i]);
while(!st.empty()&&H[st.back()]<h) {
pr[st.back()] = i;
// printf("(%d, %d): %d\n",st.back(),i-1,ith.getv(st.back(),i-1));
r[st.back()] = H[st.back()] - ith.getv(st.back(),i-1);
st.pop_back();
}
st.push_back(i);
}
st.clear();
for (int i=N-1;i>=-1;i--) {
int h = (i==-1?INF:H[i]);
while(!st.empty()&&H[st.back()]<h) {
pl[st.back()] = i;
l[st.back()] = H[st.back()] - ith.getv(i+1, st.back());
st.pop_back();
}
st.push_back(i);
}
for (int i=0;i<N;i++) {
// printf("%d: %d, %d, %d\n",i,min(l[i],r[i]),pl[i],pr[i]);
itr.upd(i, {min(l[i],r[i]), pr[i]});
itl.upd(i, {min(l[i],r[i]),pl[i]});
}
itl.calc();
itr.calc();
}
int max_towers(int L, int R, int D) {
// printf("%d, %d, %d\n",L,R,D);
int ans = itr.getv(L, R, D, 0, N)+1;
int maxih = ithm.getv(L,R);
int m = loc[maxih];
int minih = ith.getv(L,R);
if (maxih-minih<D) return 1;
{
int s = m, e = R;
while(s<=e) {
int mid = (s+e)/2;
if (ithm.getv(mid,R)-ith.getv(mid,R)>=D) s = mid+1;
else e = mid-1;
}
ans -= itr.getv(s,R,D,R+1,N);
}
{
int s = L, e = m;
while(s<=e) {
int mid = (s+e)/2;
if (ithm.getv(L,mid)-ith.getv(L,mid)>=D) e = mid-1;
else s = mid+1;
}
ans -= itl.getv(L,e,D,-1,L-1);
}
return ans;
}
