#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
const int INF = 1e9 + 7;
const int MAXN = 1e5;
struct Node{
int val;
Node(){val = -INF;}
void init(int _val){val = _val;}
};
Node merge(Node l, Node r){
Node ret; ret.init(max(l.val, r.val));
return ret;
}
bool subtask1 = true;
int n, k=0;
vector<int> h;
Node st[MAXN * 2];
void build(){
for(int i=n-1; i>0; i--) st[i] = merge(st[i<<1],st[i<<1|1]);
}
void update(int p, Node val){
for(st[p+=n] = val; p>>=1;) st[p] = merge(st[p<<1],st[p<<1|1]);
}
Node query(int l, int r){
Node resl, resr;
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1) resl=merge(resl,st[l++]);
if(r&1) resr=merge(st[--r],resr);
}
return merge(resl, resr);
}
void init(int N, vector<int> H) {
n = N;
h = H;
for(int i=1; i<n; i++){
if(h[i] < h[i-1]) break;
k = i;
}
for(int i=0; i<k; i++) subtask1 &= h[i] < h[k];
for(int i=k+1; i<n; i++) subtask1 &= h[i] < h[k];
for(int i=1; i<k; i++) subtask1 &= h[i-1] < h[i];
for(int i=k+1; i<n; i++) subtask1 &= h[i] < h[i-1];
for(int i=0; i<n; i++) st[i+n].init(h[i]);
build();
}
int max_towers(int L, int R, int D) {
if(subtask1){
if(R < k || L > k || R - L + 1 < 3 || L == k || R == k) return 1;
return (h[L] <= h[k] - D && h[R] <= h[k] - D) ? 2 : 1;
}
if (R - L + 1 < 3) return 1;
vector<pair<int,int>> q;
for(int i = L; i <= R; i++) q.pb(mp(h[i], i));
sort(all(q));
set<int> used;
used.insert(q[0].snd);
for(int i = 1; i < sz(q); i++){
bool can=true;
auto it = used.lower_bound(q[i].snd);
if(it == used.end()) it--;
int l = *it, r=q[i].snd;
if(l>r) swap(l,r);
if(r-l+1<3) can=false;
else{
int hk = query(l+1, r).val;
if(!(h[l] <= hk - D && h[r] <= hk - D))
can=false;
}
if(it != used.begin()){
it--;
l = *it, r=q[i].snd;
if(l>r) swap(l,r);
if(r-l+1<3) can=false;
else{
int hk = query(l+1, r).val;
if(!(h[l] <= hk - D && h[r] <= hk - D))
can=false;
}
}
if(can) used.insert(q[i].snd);
}
return sz(used);
}
