//#include "sphinx.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf=1e9;
const ll mod2 =1e9+7;
int n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,en;
int el = 19;
//const ll base=67;
int st[17][100001],st2[17][100001],a[100001];
struct ib
{
int a,b;
};
vector<int> ok;
vector<ib> vc;
ib d[100001];
struct segc
{
int a,b,c,d;
};
int mer(int x,int y)
{
if(a[x]>a[y])return y;
return x;
}
int mer2(int x,int y)
{
if(a[x]>a[y])return x;
return y;
}
int gg(int l,int r)
{
int k=log2(r-l+1);
return mer(st[k][l],st[k][r-mask(k)+1]);
}
int ggb(int l,int r)
{
int k=log2(r-l+1);
return a[mer2(st2[k][l],st2[k][r-mask(k)+1])];
}
void hehe(int l,int r)
{
if(l==r)return;
int mid=gg(l,r);
int dist=inf;
bool okk=0;
if(a[mid-1]<a[mid]&&mid!=1)okk=1;
if(a[mid+1]<a[mid]&&mid!=n)okk=1;
d[mid]={l-1,r+1};
if(!okk)
{
if(l!=1)
{
dist=ggb(l,mid-1);
}
if(r!=n)
{
dist=min(dist,ggb(mid+1,r));
}
ok.pb({dist-a[mid]});
vc.pb({dist-a[mid],mid});
}
if(l!=mid)
hehe(l,mid-1);
if(mid!=r)
hehe(mid+1,r);
}
struct scibidi
{
segc t[400001];
segc merc(segc a,segc b)
{
return {max(a.a,b.a),min(a.b,b.b),max({a.c,b.a-a.b,b.c}),max({a.d,b.d,a.a-b.b})};
}
void build(int node,int l,int r)
{
if(l==r)
{
t[node]= {a[l],a[l],-inf,-inf};
return;
}
int mid=l+r>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
t[node]=merc(t[node<<1],t[node<<1|1]);
}
segc get(int node,int l,int r,int l1,int r1)
{
if(l>=l1&&r<=r1)return t[node];
int mid=l+r>>1;
if(mid<l1)return get(node<<1|1,mid+1,r,l1,r1);
if(mid>=r1)return get(node<<1,l,mid,l1,r1);
return merc(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
}
} hihi;
bool cmp(ib a,ib b)
{
return a.a<b.a;
}
void init(int N,vector<int> aa)
{
n=N;
for(int i=0; i<n; i++)
a[i+1]=aa[i],st[0][i+1]=i+1,st2[0][i+1]=i+1;
hihi.build(1,1,n);
for(int i=1; i<=16; i++)
for(int j=1; j+mask(i)-1<=n; j++)
st[i][j]=mer(st[i-1][j],st[i-1][j+mask(i-1)]),
st2[i][j]=mer2(st2[i-1][j],st2[i-1][j+mask(i-1)]);
hehe(1,n);
sort(ok.begin(),ok.end());
ok.erase(unique(ok.begin(),ok.end()),ok.end());
sort(vc.begin(),vc.end(),cmp);
/**l=0;
for(int i=1;i<=ok.size();i++)
{
while(l<vc.size()&&vc[l].a==ok[i-1])
{
s3=seg.upd(s3,1,n,vc[l].b);
}
b[i]=s3;
}*/
}
int max_towers(int l,int r,int dd)
{
l++;
r++;
s4=inf;
s5=0;
dem=0;
for(auto x:vc)
if(x.a>=dd&&x.b>=l&&x.b<=r)
{
dem++;
s4=min(x.b,s4);
s5=max(s5,x.b);
}
if(dem==0)
{
s2=gg(l,r);
dem=1;
if(s2!=l)
{
s3=ggb(l,s2-1);
if(s3-dd>=s2)dem++;
}
if(s2!=r)
{
s3=ggb(s2+1,r);
if(s3-dd>=s2)dem++;
}
return dem;
}
else
{
if(d[s4].a>=l)dem++;
else
{
if(hihi.get(1,1,n,l,s4).c>=dd)dem++;
}
if(d[s5].b<=r)dem++;
else
{
if(hihi.get(1,1,n,s5,r).d>=dd)dem++;
}
return dem;
}
}
