#include <bits/stdc++.h>
using namespace std;
const int c=100005, sok=2e9+5;
int n, t[c], maxi, fixd;
bool tc1=1, fontos[c];
set<pair<int, int> > tc5;
set<int> pos;
set<pair<int, int> > dif;
int kul(int a, int b) {
return abs(t[a]-t[b]);
}
vector<vector<pair<int, int>>> rmq_mini, rmq_maxi;
vector<int> rmq_log;
void rmq_init(vector<int> sz) {
int n=sz.size();
rmq_log.resize(n+1);
for (int i=2; i<=n; i++) {
rmq_log[i]=rmq_log[i/2]+1;
}
int po=1, db=1;
while (po<=n) {
po*=2, db++;
}
rmq_mini.resize(db);
rmq_maxi.resize(db);
for (int i=0; i<db; i++) {
rmq_mini[i].resize(n);
rmq_maxi[i].resize(n);
}
for (int i=0; i<n; i++) {
rmq_mini[0][i]={sz[i], i};
rmq_maxi[0][i]={sz[i], i};
}
for (int j=1; j<db; j++) {
for (int i=0; i+(1<<j)<=n; i++) {
int s=i+(1<<(j-1));
rmq_mini[j][i]=min(rmq_mini[j-1][i], rmq_mini[j-1][s]);
rmq_maxi[j][i]=max(rmq_maxi[j-1][i], rmq_maxi[j-1][s]);
}
}
}
pair<int, int> rmq_ask(int l, int r, int id) {
int s=rmq_log[r-l+1], s2=r+1-(1<<s);
if (!id) {
return min(rmq_mini[s][l], rmq_mini[s][s2]);
} else {
return max(rmq_maxi[s][l], rmq_maxi[s][s2]);
}
}
vector<int> spec;
int try_tc46(int l, int r, int d) {
if (fixd!=0 && d!=fixd) return 0;
if (fixd==0) {
fixd=d;
int ut=sok, utid=0, id=1;
for (int i=1; i<=n+1; i++) {
if (id==1) {
if (t[i]>ut) utid=i;
ut=max(ut, t[i]);
if (ut-t[i]>=d) {
spec.push_back(utid);
utid=i;
ut=t[i];
id=0;
}
} else {
if (t[i]<ut) utid=i;
ut=min(ut, t[i]);
if (t[i]-ut>=d) {
spec.push_back(utid);
utid=i;
ut=t[i];
id=1;
}
}
}
spec.push_back(n+1);
/*cout<< "spec: ";
for (auto x:spec) cout << x << " ";
cout << "\n";*/
}
int kezd=-1, veg=-1;
int si=spec.size(), lo=0, hi=si, mid;
while (hi-lo>1) {
mid=(hi+lo)/2;
if (spec[mid]<l) lo=mid;
else hi=mid;
}
kezd=hi;
if (spec[kezd]>r) return 1;
lo=0, hi=si;
while (hi-lo>1) {
mid=(hi+lo)/2;
if (spec[mid]>r) hi=mid;
else lo=mid;
}
veg=lo;
//cout << "sikerult " << kezd << " " << veg << "\n";
assert(kezd<=veg);
int ans=(veg+1)/2-(kezd/2);
int kpos=spec[kezd], vpos=spec[veg];
if (l<kpos && kezd%2==0 && rmq_ask(l, kpos-1, 0).first+d<=t[kpos]) ans++;
if (vpos<r && veg%2==0 && rmq_ask(vpos+1, r, 0).first+d<=t[vpos]) ans++;
return ans;
}
void sub(int p) {
auto it=pos.find(p);
int el=0, kov=0;
it++;
kov=(*it);
it--, it--;
el=(*it);
//cout << "valt " << el << " " << p << " " << kov << "\n";
pos.erase(p);
dif.erase({kul(p, kov), p});
dif.erase({kul(el, p), el});
dif.insert({kul(el, kov), el});
}
void calc_tc5() {
fontos[0]=1, fontos[n+1]=1;
int ut=sok, ans=0, id=1;
for (int i=1; i<=n+1; i++) {
if (id==1) {
ut=max(ut, t[i]);
if (ut>t[i]) {
fontos[i-1]=1;
ut=t[i];
id=0;
ans++;
}
} else {
ut=min(ut, t[i]);
if (t[i]>ut) {
fontos[i-1]=1;
ut=t[i];
id=1;
}
}
}
int el=-1;
for (int i=0; i<=n+1; i++) {
if (!fontos[i]) continue;
pos.insert(i);
if (el!=-1) {
dif.insert({kul(el, i), el});
//cout << "fontos " << el << " " << i << "\n";
}
el=i;
}
tc5.insert({0, ans});
while (ans>1) {
auto it=dif.begin();
int ert=(*it).first, p=(*it).second;
auto it2=pos.upper_bound(p);
int kov=*it2;
//cout << "fontos " << p << " " << kov << "\n";
sub(p), sub(kov);
ans--;
//cout << ert << " " << ans << "\n";
it=tc5.upper_bound({ert, ans});
if (it!=tc5.end()) tc5.erase(it);
tc5.insert({ert, ans});
}
}
void init(int N, vector<int> sz) {
vector<int> sz2;
sz2.push_back(sok);
for (auto x:sz) sz2.push_back(x);
sz2.push_back(sok);
rmq_init(sz2);
n=N;
for (int i=0; i<n; i++) {
t[i+1]=sz[i];
if (t[i+1]>t[maxi]) maxi=i+1;
}
t[0]=sok, t[n+1]=sok;
for (int i=1; i<=n; i++) {
if (i<maxi && t[i]>t[i+1] || i>maxi && t[i]>t[i-1]) {
tc1=0;
}
}
calc_tc5();
}
int slow(int l, int r, int d) {
int ut=t[l]+d, ans=0, id=1;
for (int i=l; i<=r; i++) {
if (id==1) {
ut=max(ut, t[i]);
if (ut-t[i]>=d) {
ut=t[i];
id=0;
ans++;
}
} else {
ut=min(ut, t[i]);
if (t[i]-ut>=d) {
ut=t[i];
id=1;
}
}
}
return ans;
}
int max_towers(int l, int r, int d) {
l++, r++;
if (tc1) {
if (l<=maxi && maxi<=r && max(t[l], t[r])+d<=t[maxi]) return 2;
return 1;
}
if (l==1 && r==n) {
auto it=tc5.upper_bound({d, 0});
it--;
return (*it).second;
}
int x=try_tc46(l, r, d);
if (x) {
return x;
}
return slow(l, r, d);
}
