#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define clz __builtin_clz
const int N=100005,M=4000005,up=1e9;
int n,a[N],st[N],w[N],w1[N],w2[N],fa1[17][N],fa2[17][N],mx[17][N];
int cntS,rt[N];struct Seg {int vl,ch[2];}sg[M];
int qMx(int l,int r)
{
	if(l>r) return 0;int t=31-clz(r-l+1);
	return max(mx[t][l],mx[t][r-(1<<t)+1]);
}
void upd(int p,int &p1,int l,int r,int x)
{
	sg[p1=++cntS]=sg[p];++sg[p1].vl;if(l==r) return;
	if(x<=mid) upd(sg[p].ch[0],sg[p1].ch[0],l,mid,x);
	else upd(sg[p].ch[1],sg[p1].ch[1],mid+1,r,x);
}
int qSm(int p,int l,int r,int qL,int qR)
{
	if(!p || qL>qR) return 0;
	if(l>=qL && r<=qR) return sg[p].vl;int res=0;
	if(qL<=mid) res=qSm(sg[p].ch[0],l,mid,qL,qR);
	if(qR>mid) res+=qSm(sg[p].ch[1],mid+1,r,qL,qR);return res;
}
void init(int n1,vector<int> a1)
{
	n=n1;for(int i=1;i<=n;++i) a[i]=mx[0][i]=a1[i-1];
	for(int i=1;i<=n;++i)
	{
		while(st[0] && a[i]<a[st[st[0]]]) --st[0];
		fa1[0][i]=st[0]?st[st[0]]:0;st[++st[0]]=i;
		for(int j=1;j<=16;++j) fa1[j][i]=fa1[j-1][fa1[j-1][i]];
	}st[0]=0;for(int i=0;i<=16;++i) fa2[i][n+1]=n+1;
	for(int i=n;i;--i)
	{
		while(st[0] && a[i]<a[st[st[0]]]) --st[0];
		fa2[0][i]=st[0]?st[st[0]]:n+1;st[++st[0]]=i;
		for(int j=1;j<=16;++j) fa2[j][i]=fa2[j-1][fa2[j-1][i]];
	}
	for(int i=1;i<=16;++i) for(int j=1;j+(1<<i)-1<=n;++j)
		mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
	for(int i=1;i<=n;++i)
	{
		w1[i]=qMx(fa1[0][i]+1,i-1)-a[i];
		w2[i]=qMx(i+1,fa2[0][i]-1)-a[i];w[i]=min(w1[i],w2[i]);
		if(w[i]>0) upd(rt[i-1],rt[i],1,up,w[i]);else rt[i]=rt[i-1];
	}
}
bool chk(int x,int l,int r,int d)
{
	if(x<l || x>r || w[x]>=d) return 0;
	if(w1[x]<d && fa1[0][x]>=l) return 0;
	if(w2[x]<d && fa2[0][x]<=r) return 0;return 1;
}
int max_towers(int l,int r,int d)
{
	int t,t1=++r,t2=++l,res;
	res=qSm(rt[r],1,up,d,up)-qSm(rt[l-1],1,up,d,up);
	for(int i=16;i>=0;--i)
	{t=fa1[i][t1];if(t>=l && qMx(t+1,r)<a[t]+d) t1=t;}
	for(int i=16;i>=0;--i)
	{t=fa2[i][t2];if(t<=r && qMx(l,t-1)<a[t]+d) t2=t;}
	return res+chk(t1,l,r,d)+(t1!=t2 && chk(t2,l,r,d));
}