#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

const int N=100010,M=4000010;
int n,tot,cnt,las,nx[N],pre[N],h[N],rt[N],val[N],nv[N],ch[M][2],siz[M],lg[N],st[N][20],st2[N][20];
priority_queue < pair<int,int> > q;
map <int,int> mp; 
int gtmx (int l,int r) {
	int k=lg[r-l+1];
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int gtmn (int l,int r) {
	int k=lg[r-l+1];
	return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
void upd (int i) {
	nv[i]=0x3f3f3f3f;
	if (nx[i]) {nv[i]=min(nv[i],gtmx(i+1,nx[i]-1)-h[i]+1);}
	if (pre[i]) {nv[i]=min(nv[i],gtmx(pre[i]+1,i-1)-h[i]+1);}
	q.push(make_pair(-nv[i],i));
}
int modify (int rt,int l,int r,int pos,int v) {
	int p=++tot;
	siz[p]=siz[rt]+v;
	if (l==r) {return p;}
	int mid=(l+r)>>1;
	if (pos<=mid) {
		ch[p][0]=modify(ch[rt][0],l,mid,pos,v);
		ch[p][1]=ch[rt][1];
	} else {
		ch[p][0]=ch[rt][0];
		ch[p][1]=modify(ch[rt][1],mid+1,r,pos,v);
	}
	return p;
}
int query (int rt,int l,int r,int xl,int xr) {
	if (xl<=l&&r<=xr) {return siz[rt];}
	if (xr<l||r<xl) {return 0;}
	int mid=(l+r)>>1;
	return query(ch[rt][0],l,mid,xl,xr)+query(ch[rt][1],mid+1,r,xl,xr);
}
int querynx (int rt,int l,int r,int pos) {
	if (r<pos||!siz[rt]) {return n+1;}
	if (l==r) {return l;}
	int mid=(l+r)>>1,tmp=querynx(ch[rt][0],l,mid,pos);
	if (tmp<=n) {return tmp;}
	else {return querynx(ch[rt][1],mid+1,r,pos);}
}
int querypre (int rt,int l,int r,int pos) {
	if (l>pos||!siz[rt]) {return 0;}
	if (l==r) {return l;}
	int mid=(l+r)>>1,tmp=querypre(ch[rt][1],mid+1,r,pos);
	if (tmp) {return tmp;}
	else {return querypre(ch[rt][0],l,mid,pos);} 
}
void init (int N,vector <int> H) {
	n=N,las=0,val[0]=1,lg[0]=-1;
	for (int i=1;i<=n;i++) {lg[i]=lg[i>>1]+1,st[i][0]=st2[i][0]=h[i]=H[i-1],mp[h[i]]=i;}
	for (int i=1;i<=18;i++) {
		for (int j=1;j+(1<<i)-1<=n;j++) {
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
			st2[j][i]=min(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
		}
	}
	for (int i=1;i<=n;i++) {
		if ((i==1||h[i-1]>h[i])&&(i==n||h[i+1]>h[i])) {
			pre[i]=las,nx[las]=i;
			rt[0]=modify(rt[0],1,n,i,1),las=i;
		}
	}
	pre[0]=las;
	for (int i=las;i;i=pre[i]) {upd(i);}
	las=1;
	while (q.size()) {
		pair<int,int> a=q.top();
		q.pop();
		int x=a.second,v=-a.first;
		if (nv[x]!=v) {continue;}
		if (v==las) {rt[cnt]=modify(rt[cnt],1,n,x,-1);}
		else {
			val[++cnt]=las=v;
			rt[cnt]=modify(rt[cnt-1],1,n,x,-1);
		}
		nx[pre[x]]=nx[x];
		pre[nx[x]]=pre[x];
		if (pre[x]) {upd(pre[x]);}
		if (nx[x]) {upd(nx[x]);}
	}
}

int max_towers (int L, int R, int D) {
	L++,R++;
	int l=0,r=cnt;
	while (l<r) {
		int mid=(l+r+1)>>1;
		if (D>=val[mid]) {l=mid;}
		else {r=mid-1;}
	}
	int res=query(rt[l],1,n,L,R),fir=querynx(rt[l],1,n,L),las=querypre(rt[l],1,n,R);
	if (fir>R) {
		int mid=mp[gtmx(L,R)];
		if (mid>L&&mid<R&&h[mid]-gtmn(L,mid-1)>=D&&h[mid]-gtmx(mid+1,R)>=D) {res+=2;}
		else {res++;}
	} else {
		if (fir>L+1) {
			int mid=mp[gtmx(L+1,fir-1)];
			if (h[mid]-gtmn(L,mid-1)>=D) {res++;}
		}
		if (las<R-1) {
			int mid=mp[gtmx(las+1,R-1)];
			if (h[mid-gtmn(mid+1,R)]>=D) {res++;}
		}
	}
	return res;
}