# include "towers.h"
# include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,len,h[100010],minh[100010],maxdl[100010],maxdr[100010],lc[100010],rc[100010],stk[100010];
vector<int> D,DL,DR;
pair<int,int> maxd[100010];
struct SEG
{
	int Rt,lc[6000010],rc[6000010],minn[6000010],tot;
	SEG():Rt(0),tot(0){minn[0]=INF;}
	void update(int &rt,int l,int r,int x,int y)
	{
		if(!rt) rt=++tot;
		if(l==r) return minn[rt]=y,void();
		int mid=(l+r)/2;
		if(x<=mid) update(lc[rt],l,mid,x,y);
		else update(rc[rt],mid+1,r,x,y);
		minn[rt]=min(minn[lc[rt]],minn[rc[rt]]);
	}
	int query(int rt,int l,int r,int x,int y)
	{
		if(!rt || l>y || r<x) return INF;
		if(l>=x && r<=y) return minn[rt];
		int mid=(l+r)/2;
		return min(query(lc[rt],l,mid,x,y),query(rc[rt],mid+1,r,x,y));
	}
}SL,SR;
namespace SEG2
{
	int rt[100010],lc[6000010],rc[6000010],tot=0;
	struct Info
	{
		int cnt,minn,maxn;
		Info(int c=0,int mn=1e9,int mx=0):cnt(c),minn(mn),maxn(mx){}
		Info operator+(const Info &t)const{return Info(cnt+t.cnt,min(minn,t.minn),max(maxn,t.maxn));}
	}val[6000010];
	int copy(int rt)
	{
		tot++;
		tie(lc[tot],rc[tot],val[tot])=make_tuple(lc[rt],rc[rt],val[rt]);
		return tot;
	}
	void update(int &rt,int l,int r,int x)
	{
		rt=copy(rt);
		if(l==r) return val[rt]=Info(1,x,x),void();
		int mid=(l+r)/2;
		if(x<=mid) update(lc[rt],l,mid,x);
		else update(rc[rt],mid+1,r,x);
		val[rt]=val[lc[rt]]+val[rc[rt]];
	}
	Info query(int rt,int l,int r,int x,int y)
	{
		if(!rt || l>y || r<x) return Info();
		if(l>=x && r<=y) return val[rt];
		int mid=(l+r)/2;
		return query(lc[rt],l,mid,x,y)+query(rc[rt],mid+1,r,x,y);
	}
}
struct SEG3
{
	int rt[100010],lc[6000010],rc[6000010],cnt[6000010],tot;
	SEG3():tot(0){}
	int copy(int rt)
	{
		tot++;
		tie(lc[tot],rc[tot],cnt[tot])=make_tuple(lc[rt],rc[rt],cnt[rt]);
		return tot;
	}
	void update(int &rt,int l,int r,int x)
	{
		rt=copy(rt);
		if(l==r) return cnt[rt]++,void();
		int mid=(l+r)/2;
		if(x<=mid) update(lc[rt],l,mid,x);
		else update(rc[rt],mid+1,r,x);
		cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
	}
	int query(int rt,int l,int r,int x,int y)
	{
		if(!rt || l>y || r<x) return 0;
		if(l>=x && r<=y) return cnt[rt];
		int mid=(l+r)/2;
		return query(lc[rt],l,mid,x,y)+query(rc[rt],mid+1,r,x,y);
	}
}SL2,SR2;
void dfs1(int rt)
{
	if(!rt) return;
	dfs1(lc[rt]);dfs1(rc[rt]);
	minh[rt]=min(h[rt],min(minh[lc[rt]],minh[rc[rt]]));
}
void dfs2(int rt)
{
	if(!rt) return;
	maxdl[rt]=(lc[rt]?0:SL.query(SL.Rt,1,1e9,1,h[rt]-1)-h[rt]);
	maxdr[rt]=(rc[rt]?0:SR.query(SR.Rt,1,1e9,1,h[rt]-1)-h[rt]);
	if(lc[rt]) SL.update(SL.Rt,1,1e9,minh[lc[rt]],h[rt]);
	dfs2(rc[rt]);
	if(lc[rt]) SL.update(SL.Rt,1,1e9,minh[lc[rt]],INF);
	if(rc[rt]) SR.update(SR.Rt,1,1e9,minh[rc[rt]],h[rt]);
	dfs2(lc[rt]);
	if(rc[rt]) SR.update(SR.Rt,1,1e9,minh[rc[rt]],INF);
}
void init(int N,vector<int> H)
{
	n=N;
	int tp=0;
	for(int i=1;i<=n;i++)
	{
		h[i]=H[i-1];
		int c=0;
		for(;tp && h[stk[tp]]<h[i];c=stk[tp--]) rc[stk[tp]]=c;
		lc[i]=c;stk[++tp]=i;
	}
	for(int c=0;tp;c=stk[tp--]) rc[stk[tp]]=c;
	int rt=stk[1];
	minh[0]=2e9;dfs1(rt);dfs2(rt);
	D.resize(n);DL.resize(n);DR.resize(n);
	for(int i=0;i<n;i++) D[i]=min(DL[i]=maxdl[i+1],DR[i]=maxdr[i+1]);
	sort(D.begin(),D.end());D.erase(unique(D.begin(),D.end()),D.end());
	sort(DL.begin(),DL.end());DL.erase(unique(DL.begin(),DL.end()),DL.end());
	sort(DR.begin(),DR.end());DR.erase(unique(DR.begin(),DR.end()),DR.end());
	for(int i=1;i<=n;i++) maxd[i]={min(maxdl[i],maxdr[i]),i};
	sort(maxd+1,maxd+n+1);
	for(int i=D.size()-1,j=n;i>=0;i--)
	{
		SEG2::rt[i]=SEG2::rt[i+1];
		for(;j && maxd[j].first==D[i];j--) SEG2::update(SEG2::rt[i],1,n,maxd[j].second);
	}
	for(int i=1;i<=n;i++) maxd[i]={maxdl[i],i};
	sort(maxd+1,maxd+n+1);
	for(int i=DL.size()-1,j=n;i>=0;i--)
	{
		SL2.rt[i]=SL2.rt[i+1];
		for(;j && maxd[j].first==DL[i];j--) SL2.update(SL2.rt[i],1,n,maxd[j].second);
	}
	for(int i=1;i<=n;i++) maxd[i]={maxdr[i],i};
	sort(maxd+1,maxd+n+1);
	for(int i=DR.size()-1,j=n;i>=0;i--)
	{
		SR2.rt[i]=SR2.rt[i+1];
		for(;j && maxd[j].first==DR[i];j--) SR2.update(SR2.rt[i],1,n,maxd[j].second);
	}
}
int max_towers(int l,int r,int d)
{
	l++;r++;
	auto ret=SEG2::query(SEG2::rt[lower_bound(D.begin(),D.end(),d)-D.begin()],1,n,l,r);
	int le=min(ret.minn,r),ri=max(ret.maxn,l);
	return max(ret.cnt+!!SR2.query(SR2.rt[lower_bound(DR.begin(),DR.end(),d)-DR.begin()],1,n,l,le-1)+!!SL2.query(SL2.rt[lower_bound(DL.begin(),DL.end(),d)-DL.begin()],1,n,ri+1,r),1);
}