#include "towers.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
struct item{
item *l,*r;
int sum;
};
const int N=1e5+10;
const int SS=1<<17;
pitem korz[N];
int t[N],n,fau[N],seg[SS*2+10],seg2[SS*2+10],seg3[SS*2+10];
bool wl[N];
pair<int,int> prz[N],org[N];
vector<pair<int,int>> ogl;
void upd2(int a,int b){
for(a+=SS;a>0;a/=2) seg[a]=max(seg[a],b);
}
void upd3(int a,int b){
for(a+=SS;a>0;a/=2) seg2[a]=max(seg2[a],b);
}
void upd4(int a,int b){
for(a+=SS;a>0;a/=2) seg3[a]=max(seg3[a],b);
}
int qr3(int a,int b,int x,int p=0,int k=SS-1,int v=1){
if(p>b or k<a) return -1;
int sr=(p+k)/2;
if(p>=a and k<=b){
if(seg2[v]>=x){
if(p==k) return p;
if(seg2[v*2]>=x)
return qr3(a,b,x,p,sr,v*2);
else return qr3(a,b,x,sr+1,k,v*2+1);
}else return -1;
}
int val=qr3(a,b,x,p,sr,v*2);
if(val==-1) return qr3(a,b,x,sr+1,k,v*2+1);
return val;
}
int qr4(int a,int b,int x,int p=0,int k=SS-1,int v=1){
if(p>b or k<a) return -1;
int sr=(p+k)/2;
if(p>=a and k<=b){
if(seg3[v]>=x){
if(p==k) return p;
if(seg3[v*2+1]>=x)
return qr4(a,b,x,sr+1,k,v*2+1);
else return qr4(a,b,x,p,sr,v*2);
}else return -1;
}
int val=qr4(a,b,x,sr+1,k,v*2+1);
if(val==-1) return qr4(a,b,x,p,sr,v*2);
return val;
}
int qr2(int a,int b){
int res=0;
for(a+=SS-1,b+=SS+1;a/2!=b/2;a/=2,b/=2){
if(a%2==0) res=max(res,seg[a+1]);
if(b%2) res=max(res,seg[b-1]);
}
return res;
}
pitem upd(pitem v,int a,int x,int p=0,int k=SS-1){
if(p==k){
pitem xd2=new item;
xd2->l=nullptr,xd2->r=nullptr,xd2->sum=x+v->sum;
return xd2;
}
int sr=(p+k)/2;
if(a<=sr){
pitem xd=upd(v->l,a,x,p,sr);
pitem xd2=new item;
xd2->l=xd,xd2->r=v->r,xd2->sum=x+v->sum;
return xd2;
}else{
pitem xd=upd(v->r,a,x,sr+1,k);
pitem xd2=new item;
xd2->l=v->l,xd2->r=xd,xd2->sum=x+v->sum;
return xd2;
}
}
int qr1(pitem v,int a,int b,int p=0,int k=SS-1){
if(p>b or k<a) return 0;
if(p>=a and k<=b) return v->sum;
int sr=(p+k)/2;
return qr1(v->l,a,b,p,sr)+qr1(v->r,a,b,sr+1,k);
}
int Find(int a){
if(fau[a]==a) return a;
return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
a=Find(a),b=Find(b);
prz[b].se=max(prz[b].se,prz[a].se);
prz[b].fi=min(prz[b].fi,prz[a].fi);
fau[a]=b;
}
void build(int v,pitem curr){
curr->sum=0;
curr->l=nullptr,curr->r=nullptr;
if(v>=SS) return;
curr->l=new item,curr->r=new item;
build(v*2,curr->l),build(v*2+1,curr->r);
}
void init(int nn, std::vector<int> H) {
n=nn;
iota(fau,fau+1+n,0);
for(int i=1;i<=n;i++) t[i]=H[i-1],prz[i]={i,i};
vector<pair<int,int>> vp;
for(int i=1;i<=n;i++) vp.push_back({t[i],i});
sort(vp.begin(),vp.end());
for(int i=1;i<=n;i++) upd2(i,t[i]);
for(int i=n-1;i>=0;i--){
int u=vp[i].se;
wl[u]=1;
if(wl[u-1]) Union(u,u-1);
if(wl[u+1]) Union(u,u+1);
pair<int,int> pom=prz[Find(u)];
int praw=qr2(u,pom.se)-t[u],lew=qr2(pom.fi,u)-t[u];
upd3(u,praw);
upd4(u,lew);
ogl.push_back({min(lew,praw),u});
org[u]=pom;
}
sort(ogl.begin(),ogl.end());
korz[0]=new item;
build(1,korz[0]);
for(int i=0;i<(int)ogl.size();i++){
int u=ogl[i].se;
korz[i+1]=upd(korz[i],u,1);
}
}
int max_towers(int l, int r, int d) {
l++,r++;
int ind=lower_bound(ogl.begin(),ogl.end(),make_pair(d,0))-ogl.begin();
int lew=qr3(l,r,d),praw=qr4(l,r,d),res=0;
pitem k=korz[ind];
if(lew!=-1){
if(org[lew].fi<=l and qr1(k,lew,lew)==1) res++;
}
if(praw!=-1){
if(org[praw].se>=r and qr1(k,praw,praw)==1) res++;
}
res+=r-l+1-qr1(k,l,r);
return max(res,1);
}
