#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
const int MAXN=1e5+10;
const int LG=18;
const int MAXA=MAXN*(4+LG);
const int INF=2e9;
int n,a[MAXN],root[MAXN];
int t;
vector <int> d;
struct R{
int rez,l,r;
};
struct AINT_PERSISTENT{
struct node{
int st,dr;
int rez,lrez,rrez;
}aint[MAXA];
void init (){
for (int i=0;i<MAXA;++i){
aint[i]={0,0,0,INF,-1};
}
}
void update (int node, int l, int r, int prev, int pos){
if (l==r){
aint[node].rez=1;
aint[node].lrez=l;
aint[node].rrez=r;
return;
}
int mij=(l+r)/2;
if (pos<=mij){
aint[node].st=++t;
aint[node].dr=aint[prev].dr;
update (aint[node].st,l,mij,aint[prev].st,pos);
}
else{
aint[node].dr=++t;
aint[node].st=aint[prev].st;
update (aint[node].dr,mij+1,r,aint[prev].dr,pos);
}
aint[node].rez=aint[aint[node].st].rez+aint[aint[node].dr].rez;
aint[node].lrez=min (aint[aint[node].st].lrez,aint[aint[node].dr].lrez);
aint[node].rrez=max (aint[aint[node].st].rrez,aint[aint[node].dr].rrez);
}
void update (int node, int prev, int pos){
update (node,1,n,prev,pos);
}
R query (int node, int l, int r, int ql, int qr){
if (r<ql or l>qr) return {0,INF,-1};
if (ql<=l and r<=qr){
return {aint[node].rez,aint[node].lrez,aint[node].rrez};
}
int mij=(l+r)/2;
R rez1=query (aint[node].st,l,mij,ql,qr);
R rez2=query (aint[node].dr,mij+1,r,ql,qr);
R rez;
rez.rez=rez1.rez+rez2.rez;
rez.l=min (rez1.l,rez2.l);
rez.r=max (rez1.r,rez2.r);
return rez;
}
R query (int node, int l, int r){
return query (node,1,n,l,r);
}
}pst;
struct AINT{
int aint[4*MAXN];
int p[4*MAXN];
void update (int node, int l, int r, int pos, int x){
if (r<pos or l>pos) return;
if (l==r){
aint[node]=x;
p[node]=l;
return;
}
int mij=(l+r)/2;
update (2*node,l,mij,pos,x);
update (2*node+1,mij+1,r,pos,x);
aint[node]=max (aint[2*node],aint[2*node+1]);
if (aint[node]==aint[2*node+1]) p[node]=p[2*node+1];
else p[node]=p[2*node];
}
void update (int pos, int x){
update (1,1,n,pos,x);
}
int query (int node, int l, int r, int ql, int qr){
if (r<ql or l>qr) return 0;
if (ql<=l and r<=qr){
return aint[node];
}
int mij=(l+r)/2;
int rez1=query (2*node,l,mij,ql,qr);
int rez2=query (2*node+1,mij+1,r,ql,qr);
return max (rez1,rez2);
}
int query (int l, int r){
return query (1,1,n,l,r);
}
pair <int,int> query2 (int node, int l, int r, int ql, int qr){
if (r<ql or l>qr) return {-INF,0};
if (ql<=l and r<=qr){
return {aint[node],p[node]};
}
int mij=(l+r)/2;
pair <int,int> rez1=query2 (2*node,l,mij,ql,qr);
pair <int,int> rez2=query2 (2*node+1,mij+1,r,ql,qr);
return max (rez1,rez2);
}
int query2 (int l, int r){
return query2 (1,1,n,l,r).second;
}
}max_st,l_st,r_st,min_st;
int get_pos (int dcrt){
return lower_bound (d.begin (),d.end (), dcrt)-d.begin ();
}
int l[MAXN],r[MAXN],dif[MAXN];
vector <int> g[MAXN];
void preclr (){
stack <int> st;
st.push (0);
for (int i=1;i<=n;++i){
while (a[i]<=a[st.top ()]) st.pop ();
l[i]=st.top ();
st.push (i);
}
while (!st.empty ()) st.pop ();
st.push (n+1);
for (int i=n;i>=1;--i){
while (a[i]<=a[st.top ()]) st.pop ();
r[i]=st.top ();
st.push (i);
}
}
void init (int N, vector <int> h){
n=N;
for (int i=0;i<n;++i) a[i+1]=h[i];
preclr ();
for (int i=1;i<=n;++i){
max_st.update (i,a[i]);
min_st.update (i,-a[i]);
}
vector <int> aux;
for (int i=1;i<=n;++i){
int lcrt=max_st.query (max (1,l[i]),i)-a[i];
int rcrt=max_st.query (i,min (n,r[i]))-a[i];
dif[i]=min (lcrt,rcrt);
l_st.update (i,lcrt);
r_st.update (i,rcrt);
aux.push_back (dif[i]);
}
sort (aux.begin (),aux.end ());
for(int i=0;i<aux.size ();++i){
if (i==0 or aux[i]!=aux[i-1]){
d.push_back (aux[i]);
}
}
for (int i=1;i<=n;++i){
g[get_pos (dif[i])].push_back (i);
}
pst.init ();
root[d.size()]=0;
for (int i=d.size ()-1;i>=0;--i){
root[i]=++t;
for (auto x:g[i]){
pst.update (root[i],root[i+1],x);
}
}
}
int max_towers (int l, int r, int d){
l++;
r++;
int crt=get_pos (d);
R p=pst.query (root[crt],l,r);
if (p.r==-1){
p.rez=1;
p.l=p.r=min_st.query2 (l,r);
}
if (l<=p.l-1 and r_st.query (l,p.l-1)>=d) p.rez++;
if (p.r+1<=r and l_st.query (p.r+1,r)>=d) p.rez++;
return p.rez;
}
