#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
const int N=2000000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],pas,L,R,D,seg[400009],l,r,z,za,PI,bo[100009],VAL[100009],pr[100009],counter,fen[200009],fen2[200009],K[100009],HD[1000009],lf[100009],rg[100009],aris[100009];
int segLF[400009],segRG[400009],segaris[400009];
map <int, int> m;
map <int, int>::iterator TA;
vector <pair <int, int> > ANS;
multiset <int> s;
multiset <int>::iterator it,tt;
multiset <pair <int, int> > S;
multiset <pair <int, int> >::iterator IT,TT;
pair <int, int> P[100009];
//
void upd(int q, int w){
q=200003-q;
while(q<=200005){
fen[q]=min(fen[q],w);
q=q+(q&(-q));
}
}
int READ(int q){
q=200003-q;
int sm=200007;
while(q>0){
sm=min(sm,fen[q]);
q=q-(q&(-q));
}
return sm;
}
void upd2(int q, int w){
q=200003-q;
while(q<=200005){
fen2[q]=max(fen2[q],w);
q=q+(q&(-q));
}
}
int read2(int q){
q=200003-q;
int sm=0;
while(q>0){
sm=max(sm,fen2[q]);
q=q-(q&(-q));
}
return sm;
}
void upd3(int q, int w){
while(q<=200005){
fen[q]=max(fen[q],w);
q=q+(q&(-q));
}
}
int read3(int q){
int sm=0;
while(q>0){
sm=max(sm,fen[q]);
q=q-(q&(-q));
}
return sm;
}
//
void read(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,seg[rr]);
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void readLF(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,segLF[rr]);
return;
}
readLF(q,(q+w)/2,rr*2);
readLF((q+w)/2+1,w,rr*2+1);
}
void readRG(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=min(z,segRG[rr]);
return;
}
readRG(q,(q+w)/2,rr*2);
readRG((q+w)/2+1,w,rr*2+1);
}
void readaris(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,segaris[rr]);
return;
}
readaris(q,(q+w)/2,rr*2);
readaris((q+w)/2+1,w,rr*2+1);
}
//
void UPD(int i){
int D;
multiset <int>::iterator it,tt;
multiset <pair <int, int> >::iterator IT,TT;
tt=s.lower_bound(i);
tt++;
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
e=z;
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
e=min(e,z);
S.erase({VAL[i],i});
S.insert({e-f[i]+1,i});
VAL[i]=e-f[i]+1;
}
void init(int NN, std::vector<int> HH) {
a=NN;
for(i=1; i<=a; i++){
f[i]=HH[i-1];
}
}
int max_towers(int LL, int RR, int DD) {
counter++;
if(counter==1){
za=1;D=DD;
while(za<a) za*=2;
for(i=1; i<=a; i++){
seg[za+i-1]=f[i];
}
for(i=za-1; i>=1; i--){
seg[i]=max(seg[i*2],seg[i*2+1]);
}
for(i=1; i<=a; i++){
PI++;P[PI]={f[i],i};
}
sort(P+1,P+PI+1);
for(ii=1; ii<=PI; ii++){
i=P[ii].second;
tt=s.lower_bound(i);
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
e=0;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
if(z<f[i]+D){
e++;
}
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
if(z<f[i]+D){
e++;
}
if(e>0) continue;
//cout<<i<<" "<<z<<" "<<f[i]<<" "<<D<<"\n";
s.insert(i);bo[i]=1;
}
for(i=1; i<=a; i++){
pr[i]=pr[i-1]+bo[i];
}
/*for(i=1; i<=a; i++){
cout<<pr[i]<<" pr ";
}
cout<<"\n";*/
//
m.clear();
for(i=1; i<=a; i++){
m[f[i]]=1;m[f[i]+D]=1;
}
zx=0;
for(TA=m.begin(); TA!=m.end(); TA++){
zx++;
(*TA).second=zx;
}
for(i=1; i<=a; i++){
HD[i]=m[f[i]+D];
K[i]=m[f[i]];
}
for(i=1; i<=a; i++){
lf[i]=read2(HD[i]);
upd2(K[i],i);
}
/*for(i=1; i<=a; i++){
cout<<lf[i]<<" lf ";
}
cout<<"\n";*/
for(i=0; i<=200007; i++){
fen[i]=a+1;
}
for(i=a; i>=1; i--){
rg[i]=READ(HD[i]);
upd(K[i],i);
}
for(i=1; i<=a; i++){
segLF[za+i-1]=lf[i];
}
for(i=za-1; i>=1; i--){
segLF[i]=max(segLF[i*2],segLF[i*2+1]);
}
for(i=1; i<=a; i++){
segRG[za+i-1]=rg[i];
}
for(i=za-1; i>=1; i--){
segRG[i]=min(segRG[i*2],segRG[i*2+1]);
}
//return 0;
for(i=0; i<=200007; i++){
fen[i]=fen2[i]=0;
}
for(i=1; i<=a; i++){
aris[i]=read2(HD[i]);
zx=read3(K[i]);
/*cout<<i<<" "<<zx<<"\n";
cout<<K[i]<<" "<<HD[i]<<"\n";*/
upd2(K[i],zx);
upd3(HD[i],i);
}
//return 0;
for(i=1; i<=a; i++){
segaris[za+i-1]=aris[i];
}
for(i=za-1; i>=1; i--){
segaris[i]=max(segaris[i*2],segaris[i*2+1]);
}
//return 0;
}
//
pas=1;LL++;RR++;
L=LL;R=RR;D=DD;
if(L==R) return 1;
zx=pr[R]-pr[L-1];
//cout<<zx<<"\n";
it=s.lower_bound(L);
l=L;r=lf[(*it)]-1;z=a+2;
if(l<=r) readRG(1,za,1);
if(z<(*it)) zx++;
it=s.lower_bound(R+1);
if(it!=s.end()){
it--;
l=rg[(*it)]+1;r=R;z=0;
if(l<=r) readLF(1,za,1);
if((*it)<z) zx++;
}
pas=max(pas,zx);
//da-check-e 2-ic tu sheidzleba
l=L;r=R;z=0;
readaris(1,za,1);
if(z>=L) pas=max(pas,2);
return pas;
}
