#include <bits/stdc++.h>
#define N 200005
#define ll long long
#define sz(s) (int)s.size()
#define ff first
#define ss second
using namespace std;
ll n;
bool tr = 0;
vector <int> h;
vector <pair<int,int>> a;
void init(int N1, vector<int> H){
n = N1;
h = H;
return;
}
int max_towers(int l, int r, int d){
if(tr == 0){
tr = 1;
a.clear();
for(int i = 0; i < n; i++) a.push_back({-1,n});
vector <int> v;
for(int i = 0; i < n; i++){
while(sz(v) > 0 and h[v.back()] >= h[i]){
v.pop_back();
}
int l1 = 0, r1 = sz(v)-1, k = -1;
while(l1 <= r1){
int md = (l1+r1) / 2;
if(h[v[md]] <= h[i]-d){
l1 = md+1;
k = md;
}
else {
r1 = md-1;
}
}
if(k != -1){
a[i].ff = v[k];
}
v.push_back(i);
}
v.clear();
for(int i = n-1; i >= 0; i--){
while(sz(v) > 0 and h[v.back()] >= h[i]){
v.pop_back();
}
int l1 = 0, r1 = sz(v)-1, k = -1;
while(l1 <= r1){
int md = (l1+r1) / 2;
if(h[v[md]] <= h[i]-d){
l1 = md+1;
k = md;
}
else {
r1 = md-1;
}
}
if(k != -1){
a[i].ss = v[k];
}
v.push_back(i);
}
}
int x = 2;
x = min(x,(r-l+1));
for(int i = l; i <= r; i++){
if(a[i].ff >= l and a[i].ss <= r){
x = 3;
break;
}
}
return x;
}
