#include "towers.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
using namespace std;
const int inf=1e18;
const int N=100005;
namespace 
{
	int n;
	int mx[N][21],lst[N][21],nxt[N][21];
	int rt[N];
	int a[N],d[N];
	int qrymx(int l,int r)
	{
		if (l>r) return -inf;
		int t=__lg(r-l+1);
		return max(mx[l][t],mx[r-(1<<t)+1][t]);
	}
	int cnt,tr[N*32],ls[N*32],rs[N*32];
	void update(int &k,int lst,int l,int r,int x,int y)
	{
		k=++cnt;
		tr[k]=tr[lst],ls[k]=ls[lst],rs[k]=rs[lst];
		tr[k]+=y;
		if (l==r) return;
		int mid=l+(r-l)/2;
		if (x<=mid) update(ls[k],ls[lst],l,mid,x,y);
		else update(rs[k],rs[lst],mid+1,r,x,y);
	}
	inline int query(int k,int lst,int l,int r,int L,int R)
	{
		if (L<=l&&r<=R) return tr[k]-tr[lst];
		int mid=l+(r-l)/2;
		int res=0;
		if (L<=mid) res+=query(ls[k],ls[lst],l,mid,L,R);
		if (R>mid) res+=query(rs[k],rs[lst],mid+1,r,L,R);
		return res;
	}
}
void init(signed nn, std::vector<signed> g)
{
	n=nn;
	for (int i=0;i<sz(g);i++)
		a[i+1]=g[i];
	for (int i=1;i<=n;i++)
		mx[i][0]=a[i];
	for (int j=1;j<=20;j++)
		for (int i=1;i+(1<<j)-1<=n;i++)
			mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
	poly sta;
	for (int i=1;i<=n;i++) d[i]=1e9,lst[i][0]=0,nxt[i][0]=n+1;
	nxt[n+1][0]=n+1,lst[0][0]=0;
	for (int i=1;i<=n;i++)
	{
		while (!sta.empty()&&a[sta.back()]>a[i])
			sta.pop_back();
		if (!sta.empty()) lst[i][0]=sta.back(),d[i]=min(d[i],qrymx(lst[i][0]+1,i-1)-a[i]);
		sta.push_back(i);
	}
	poly().swap(sta);
	for (int i=n;i>=1;i--)
	{
		while (!sta.empty()&&a[sta.back()]>a[i]) 
			sta.pop_back();
		if (!sta.empty()) 
			nxt[i][0]=sta.back(),d[i]=min(d[i],qrymx(i+1,nxt[i][0]-1)-a[i]);
		sta.push_back(i);
	}
	for (int i=1;i<=n;i++)	
		d[i]=max(d[i],0ll),update(rt[i],rt[i-1],0,1000000000,d[i],1);
	// for (int i=1;i<=n;i++)	 cout<<d[i]<<",";
	// cout<<endl;
	for (int j=1;j<=20;j++)
		for (int i=0;i<=n+1;i++) lst[i][j]=lst[lst[i][j-1]][j-1],nxt[i][j]=nxt[nxt[i][j-1]][j-1];
}
signed max_towers(signed L, signed R, signed D)
{
	L++,R++;

	int l=L,r=R;
	for (int i=20;i>=0;i--)
		if (nxt[l][i]<=n&&qrymx(L,nxt[l][i]-1)<a[nxt[l][i]]+D)
		{
			l=nxt[l][i];
		}
	for (int i=20;i>=0;i--)
		if (lst[r][i]>=1&&qrymx(lst[r][i]+1,R)<a[lst[r][i]]+D)
			r=lst[r][i];
	if (l>=R) return 1;
	int res=(qrymx(l+1,nxt[l][0]-1)-a[l]>=D)+(qrymx(lst[r][0]+1,r-1)-a[r]>=D);
	return res+query(rt[r-1],rt[l],0,1000000000,D,1000000000);
}