/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include"towers.h"
int n,k=-1;
vector<int>h,vv;
map<int,int>val;
void init(int N,vector<int>H){
n=N;h=H;
{
vv=h;
sort(vv.begin(),vv.end());
for(int i=0;i<vv.size();i++)val[vv[i]]=i;
}
int l=1,r=n-2;
while(l<n&&h[l-1]<=h[l])l++;l--;
while(r>=0&&h[r]>=h[r+1])r--;r++;
if(l==r)k=l;
}
struct sgt{
vector<int>s;
int lg,sz;
sgt(int N){
lg=__lg(N)+1;
sz=1<<lg;
s.assign(sz*2,0);
}
void edit(int i,int v){
i+=sz;s[i]=v;
while(i>1){
i>>=1;
s[i]=max(s[i*2],s[i*2+1]);
}
}
int get(int L,int R,int l,int r,int i){
if(L>R||l>R||L>r)return 0;
if(L<=l&&r<=R)return s[i];
return max(get(L,R,l,(l+r)/2,i*2),get(L,R,(l+r)/2+1,r,i*2+1));
}
int get(int l){return get(++l,sz,1,sz,1);}
};
struct sgtt{
vector<int>s;
int lg,sz;
sgtt(int N){
lg=__lg(N)+1;
sz=1<<lg;
s.assign(sz*2,0);
}
void edit(int L,int R,int mx,int l,int r,int i){
if(L>R||l>R||L>r)return;
if(L<=l&&r<=R){s[i]=max(s[i],mx);return;}
edit(L,R,mx,l,(l+r)/2,i*2);
edit(L,R,mx,(l+r)/2+1,r,i*2+1);
}
void edit(int i,int mx){edit(i+1,sz,mx,1,sz,1);}
int get(int i){
i+=sz;
int ret=0;
while(i){
ret=max(ret,s[i]);
i>>=1;
}
return ret;
}
};
int max_towers(int l,int r,int dd){
if(k!=-1)return(l<=k&&k<=r&&max(h[l]+dd,h[r]+dd)<=h[k])+1;
vector<int>d(n,0);
sgt s(n+5);
sgtt p(n+5);
for(int i=l;i<=r;i++){
int j=lower_bound(vv.begin(),vv.end(),h[i]+dd)-vv.begin();
if(j==vv.size())d[i]=1;
else{
j=val[vv[j]];
d[i]=s.get(j)+1;
p.edit(j,d[i]);
}
s.edit(val[h[i]],p.get(val[h[i]]));
}
return *max_element(d.begin(),d.end());
}
