#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int n, vl[nx];
vector<int> h={0};
vector<pair<int, int>> srt;
struct persistsegtree
{
struct node
{
int sm;
node *l, *r;
node(int sm=0): sm(sm), l(l), r(r){}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &k)
{
k=new node();
if (l==r) return;
int md=(l+r)/2;
build(l, md ,k->l);
build(md+1, r, k->r);
}
void update(int l, int r, pnode &k, pnode p, int idx)
{
k=new node(*p);
if (l==r) return k->sm++, void();
int md=(l+r)/2;
if (idx<=md) update(l, md, k->l, p->l, idx);
else update(md+1, r, k->r, p->r, idx);
k->sm=k->l->sm+k->r->sm;
}
int getsum(int l, int r, pnode k, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return k->sm;
int md=(l+r)/2;
return getsum(l, md, k->l, ql, qr)+getsum(md+1, r, k->r, ql, qr);
}
int getfirstleft(int l, int r, pnode k, int idx)
{
if (idx<l||k->sm==0) return 0;
if (l==r) return l;
int md=(l+r)/2;
int rvl=getfirstleft(md+1, r, k->r, idx);
return rvl?rvl:getfirstleft(l, md, k->l, idx);
}
int getfirstright(int l, int r, pnode k, int idx)
{
if (r<idx||k->sm==0) return 0;
if (l==r) return l;
int md=(l+r)/2;
int lvl=getfirstright(l, md, k->l, idx);
return lvl?lvl:getfirstright(md+1, r, k->r, idx);
}
} p;
struct segtree
{
struct node
{
int mx, mn, difl, difr;
node(int mx=0, int mn=1e9, int difl=0, int difr=0): mx(mx), mn(mn), difl(difl), difr(difr){}
} d[4*nx];
node merge(node l, node r)
{
node res;
res.mx=max(l.mx, r.mx);
res.mn=min(l.mn, r.mn);
res.difl=max({l.difl, r.difl, r.mx-l.mn});
res.difr=max({l.difr, r.difr, l.mx-r.mn});
return res;
}
void build(int l, int r, int i)
{
if (l==r) return d[i]=node(h[l], h[l]), void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=merge(d[2*i], d[2*i+1]);
}
int getmax(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i].mx;
int md=(l+r)/2;
return max(getmax(l, md, 2*i, ql, qr), getmax(md+1, r, 2*i+1, ql, qr));
}
int getlessleft(int l, int r, int i, int idx, int vl)
{
if (idx<l||d[i].mn>=vl) return 0;
if (l==r) return l;
int md=(l+r)/2;
int rvl=getlessleft(md+1, r, 2*i+1, idx, vl);
return rvl?rvl:getlessleft(l, md, 2*i, idx, vl);
}
int getgreaterleft(int l, int r, int i, int idx, int vl)
{
if (idx<l||d[i].mx<vl) return 0;
if (l==r) return l;
int md=(l+r)/2;
int rvl=getgreaterleft(md+1, r, 2*i+1, idx, vl);
return rvl?rvl:getgreaterleft(l, md, 2*i, idx, vl);
}
int getlessright(int l, int r, int i, int idx, int vl)
{
if (r<idx||d[i].mn>=vl) return 0;
if (l==r) return l;
int md=(l+r)/2;
int lvl=getlessright(l, md, 2*i, idx, vl);
return lvl?lvl:getlessright(md+1, r, 2*i+1, idx, vl);
}
int getgreaterright(int l, int r, int i, int idx, int vl)
{
if(r<idx||d[i].mx<vl) return 0;
if (l==r) return l;
int md=(l+r)/2;
int lvl=getgreaterright(l, md, 2*i, idx, vl);
return lvl?lvl:getgreaterright(md+1, r, 2*i+1, idx, vl);
}
node getmaxdif(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return node();
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return merge(getmaxdif(l, md, 2*i, ql, qr), getmaxdif(md+1, r, 2*i+1, ql, qr));
}
} s;
void init(int N, std::vector<int> H) {
n=N;
for (int i=0; i<n;i ++) h.push_back(H[i]);
s.build(1, n, 1);
for (int i=1; i<=n; i++)
{
int cl=s.getlessleft(1, n, 1, i, h[i]), cr=s.getlessright(1, n, 1, i, h[i]), f=0;
if (cl&&cl+1==i) f=1;
if (cr&&cr-1==i) f=1;
if (!f)
{
if (cl&&cr) srt.push_back({min(s.getmax(1, n, 1, cl+1, i-1), s.getmax(1, n, 1, i+1, cr-1))-h[i], i});
else if (cr) srt.push_back({s.getmax(1, n, 1, i+1, cr-1)-h[i], i});
else if (cl) srt.push_back({s.getmax(1, n, 1, cl+1, i-1)-h[i], i});
else srt.push_back({2e9, i});
}
}
sort(srt.begin(), srt.end());
p.build(1, n, p.rt[srt.size()]);
for (int i=srt.size()-1; i>=0; i--) p.update(1, n, p.rt[i], p.rt[i+1], srt[i].second);
}
int max_towers(int L, int R, int D) {
L++, R++;
int idx=lower_bound(srt.begin(), srt.end(), make_pair(D, 0))-srt.begin();
int curans=p.getsum(1, n, p.rt[idx], L, R);
if (curans==0)
{
auto tmp=s.getmaxdif(1, n, 1, L, R);
if (tmp.difl>=D&&tmp.difr>=D) return 2;
else return 1;
}
int lidx=p.getfirstright(1, n, p.rt[idx], L);
if (s.getmax(1, n, 1, L, lidx)>=h[lidx]+D)
{
int tidx=s.getgreaterleft(1, n, 1, lidx, h[lidx]+D);
if (s.getmaxdif(1, n, 1, L, tidx).difl>=D) curans++;
}
int ridx=p.getfirstleft(1, n, p.rt[idx], R);
if (s.getmax(1, n, 1, ridx, R)>=h[ridx]+D)
{
int tidx=s.getgreaterright(1, n, 1, ridx, h[ridx]+D);
if (s.getmaxdif(1, n, 1, tidx, R).difr>=D) curans++;
}
return curans;
}
