#include"towers.h"
#include<bits/stdc++.h>
#define N 100005
#define W 19

struct node{
	int val;
	node *son[2];
	node(){
		val=0,son[0]=son[1]=0;
	}
};
inline node *ins(node *q,int L,int R,int x){
	node *p=new node();
	if(q)
		*p=*q;
	p->val++;
	if(L==R)
		return p;
	int mid=(L+R)>>1;
	x<=mid?p->son[0]=ins(p->son[0],L,mid,x):p->son[1]=ins(p->son[1],mid+1,R,x);
	return p;
}
inline int sum(node *p,int L,int R,int l,int r){
	if(L>r||R<l||!p)
		return 0;
	if(l<=L&&R<=r)
		return p->val;
	int mid=(L+R)>>1;
	return sum(p->son[0],L,mid,l,r)+sum(p->son[1],mid+1,R,l,r);
}

node *rt[N],*F[N],*G[N];

int n,a[N];

int lg[N],st[N][W];
inline int mx(int L,int R){
	if(!L||R>n)
		return 1e9;
	int k=lg[R-L+1];
	return std::max(st[L][k],st[R-(1<<k)+1][k]);
}

int l[N][W],r[N][W];
std::stack<int> s;

int f[N],g[N],h[N];

void init(int n_,std::vector<int> A){
	n=n_;
	for(int i=1;i<=n;i++)
		a[i]=A[i-1];
	lg[0]=-1;
	for(int i=1;i<=n;i++)
		lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)
		st[i][0]=a[i];
	for(int j=1;j<W;j++) for(int i=1;i+(1<<j)-1<=n;i++)
		st[i][j]=std::max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=n;i++){
		while(s.size()&&a[s.top()]>a[i])
			r[s.top()][0]=i,s.pop();
		s.emplace(i);
	}
	while(s.size())
		r[s.top()][0]=n+1,s.pop();
	r[n+1][0]=n+1;
	for(int i=n;i;i--){
		while(s.size()&&a[s.top()]>a[i])
			l[s.top()][0]=i,s.pop();
		s.emplace(i);
	}
	while(s.size())
		l[s.top()][0]=0,s.pop();
	l[0][0]=0;
	for(int j=1;j<W;j++) for(int i=0;i<=n+1;i++)
		l[i][j]=l[l[i][j-1]][j-1],r[i][j]=r[r[i][j-1]][j-1];
	for(int i=1;i<=n;i++)
		f[i]=mx(l[i][0],i)-a[i],g[i]=mx(i,r[i][0])-a[i],h[i]=std::min(f[i],g[i]);
	for(int i=1;i<=n;i++)
		rt[i]=ins(rt[i-1],0,1e9,h[i]);
	for(int i=n;i;i--)
		G[i]=ins(G[r[i][0]],0,1e9,g[i]);
	for(int i=1;i<=n;i++)
		F[i]=ins(F[l[i][0]],0,1e9,f[i]);
//	for(int i=1;i<=n;i++)
//		printf("%d ",h[i]);
//	puts("");
//	for(int i=1;i<=n;i++)
//		printf("%d ",sum(rt[i],0,1e9,0,1e9));
//	puts("");
}

int max_towers(int L,int R,int D){
	if(L==R)
		return 1;
	L++,R++;
//	printf("?%d %d %d\n",L,R,D);
	int res=sum(rt[R],0,1e9,D,1e9)-sum(rt[L-1],0,1e9,D,1e9);
//	printf("*%d\n",res);
	int u=L;
	for(int i=W-1;~i;i--) if(r[r[u][i]][0]<=R&&f[r[u][i]]<D)
		u=r[u][i];
	if(r[u][0]<=R&&f[u]<D)
//		printf("@%d %d\n",u,r[u][0]),
		res+=sum(G[L],0,1e9,D,1e9)-sum(G[r[u][0]],0,1e9,D,1e9);
	u=R;
	for(int i=W-1;~i;i--) if(l[l[u][i]][0]>=L&&g[l[u][i]]<D)
		u=l[u][i];
	if(l[u][0]>=L&&g[u]<D)
		res+=sum(F[R],0,1e9,D,1e9)-sum(F[l[u][0]],0,1e9,D,1e9);
	if(l[u][0]>=L)
		u=l[u][0];
	if(h[u]<D)
		res++;
	return res;
}