#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include "towers.h"
#define inf 2000000000
using namespace std;
int n,h[100005];
int tot,s[100005];
struct node{
	int l,r,val;
	node(){
		l=r=val=0;
		return;
	}
}tree[5000005];
int cnt,rt[100005];
int log_2[100005],st[100005][25];
int q[100005],tail;
int pl[100005],pr[100005];
vector<int> e[100005];
int st_ask(int l,int r){
	if (l>r)return inf;
	int w=log_2[r-l+1];
	return min(st[l][w],st[r-(1<<w)+1][w]);
}
int larger(int x){
	int l=1,r=tot,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if (s[mid]>=x)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
void ins(int &now,int nowl,int nowr,int pos){
	int pre=now;
	now=++cnt;
	tree[now]=tree[pre];
	tree[now].val++;
	if (nowl==nowr)return;
	int mid=(nowl+nowr)/2;
	if (pos<=mid)ins(tree[now].l,nowl,mid,pos);
	else ins(tree[now].r,mid+1,nowr,pos);
	return;
}
int sgt_ask(int now,int nowl,int nowr,int lt,int rt){
	if (now==0)return 0;
	if (nowl>=lt&&nowr<=rt)return tree[now].val;
	int mid=(nowl+nowr)/2,s=0;
	if (mid>=lt)s+=sgt_ask(tree[now].l,nowl,mid,lt,rt);
	if (mid+1<=rt)s+=sgt_ask(tree[now].r,mid+1,nowr,lt,rt);
	return s;
}
void init(int _n,vector<int> _h){
	n=_n;
	for (int i=1;i<=n;i++)h[i]=_h[i-1];
	h[0]=h[n+1]=inf;
	for (int i=2;i<=n;i++)log_2[i]=log_2[i/2]+1;
	for (int i=1;i<=n;i++)st[i][0]=h[i];
	for (int w=1;(1<<w)<=n;w++)
		for (int i=1;i+(1<<w)-1<=n;i++)
			st[i][w]=min(st[i][w-1],st[i+(1<<(w-1))][w-1]);
	tail=0;
	q[0]=0;
	for (int i=1;i<=n;i++){
		while(tail>0&&h[q[tail]]<=h[i])tail--;
		pl[i]=q[tail];
		q[++tail]=i;
	}
	tail=0;
	q[0]=n+1;
	for (int i=n;i>=1;i--){
		while(tail>0&&h[q[tail]]<h[i])tail--;
		pr[i]=q[tail];
		q[++tail]=i;
	}
	for (int i=1;i<=n;i++)s[++tot]=h[i]-max(st_ask(pl[i]+1,i-1),st_ask(i+1,pr[i]-1));
	sort(s+1,s+1+tot);
	for (int i=1;i<=n;i++)e[larger(h[i]-max(st_ask(pl[i]+1,i-1),st_ask(i+1,pr[i]-1)))].push_back(i);
	for (int i=tot;i>=1;i--){
		rt[i]=rt[i+1];
		for (int j=0;j<(int)e[i].size();j++)ins(rt[i],1,n,e[i][j]);
	}
	return;
}
int max_towers(int l,int r,int d){
	l++,r++;
	d=larger(d);
	int ans=sgt_ask(rt[d],1,n,l,r);
	if (ans==0)return 1;
	int ql=l,qr=r,pos=0;
	while(ql<=qr){
		int mid=(ql+qr)/2;
		if (sgt_ask(rt[d],1,n,l,mid)>0)pos=mid,qr=mid-1;
		else ql=mid+1;
	}
	if (h[pos]-max(st_ask(max(l,pl[pos]+1),pos-1),st_ask(pos+1,min(r,pr[pos]-1)))<d)ans--;
	if (ans>0){
		ql=l,qr=r,pos=0;
		while(ql<=qr){
			int mid=(ql+qr)/2;
			if (sgt_ask(rt[d],1,n,mid,r)>0)pos=mid,ql=mid+1;
			else qr=mid-1;
		}
		if (h[pos]-max(st_ask(max(l,pl[pos]+1),pos-1),st_ask(pos+1,min(r,pr[pos]-1)))<d)ans--;
	}
	return ans+1;
}