#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 1e5 + 5;
const int INF = 2e9;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
struct Node{
int cnt, l, r;
Node(){
this->cnt = 0;
this->l = this->r = -1;
}
};
int n, l_min[lim], r_min[lim], h[lim], log_v[lim], st_dif[lim << 2], spt_max[lim][17], spt_min[lim][17];
vector<Node>st;
vector<pair<int, int>>a(1, make_pair(INF, -1));
int get_min(int l, int r){
int k = log_v[r - l + 1];
return min(spt_min[l][k], spt_min[r - (1 << k) + 1][k]);
}
int get_max(int l, int r){
int k = log_v[r - l + 1];
return max(spt_max[l][k], spt_max[r - (1 << k) + 1][k]);
}
void update(int id, int p){
int l = 1, r = n;
while(l < r){
st[id].cnt++;
int m = (l + r) >> 1;
if(m < p){
st.emplace_back(st[st[id].r]);
st[id].r = int(st.size()) - 1;
id = st[id].r;
l = m + 1;
}
else{
st.emplace_back(st[st[id].l]);
st[id].l = int(st.size()) - 1;
id = st[id].l;
r = m;
}
}
st[id].cnt++;
}
void build(int id = 0, int l = 1, int r = n){
if(l == r){
return;
}
st[id].l = st.size();
st.emplace_back(Node());
st[id].r = st.size();
st.emplace_back(Node());
int m = (l + r) >> 1;
build(st[id].l, l, m);
build(st[id].r, m + 1, r);
}
void build_dif(int id = 1, int l = 1, int r = n){
if(l == r){
st_dif[id] = 0;
return;
}
int m = (l + r) >> 1;
build_dif(id << 1, l, m);
build_dif(id << 1 | 1, m + 1, r);
st_dif[id] = max({st_dif[id << 1], st_dif[id << 1 | 1], get_max(m + 1, r) - get_min(l, m)});
}
int get_dif(int u, int v, int id = 1, int l = 1, int r = n){
if(l > v || r < u || u > v){
return 0;
}
if(u <= l && v >= r){
return st_dif[id];
}
int m = (l + r) >> 1;
if(m >= v){
return get_dif(u, v, id << 1, l, m);
}
if(m < u){
return get_dif(u, v, id << 1 | 1, m + 1, r);
}
int temp = max({get_dif(u, v, id << 1, l, m), get_dif(u, v, id << 1 | 1, m + 1, r), get_max(m + 1, v) - get_min(u, m)});
return temp;
}
void init(int N, vector<int>H){
log_v[0] = -1;
for(int i = 1; i < lim; i++){
log_v[i] = log_v[i >> 1] + 1;
}
n = N;
for(int i = 0; i < n; i++){
spt_max[i + 1][0] = spt_min[i + 1][0] = h[i + 1] = H[i];
}
for(int j = 1; j < 17; j++){
for(int i = 1; i + (1 << j) - 1 <= n; i++){
spt_min[i][j] = min(spt_min[i][j - 1], spt_min[i + (1 << (j - 1))][j - 1]);
spt_max[i][j] = max(spt_max[i][j - 1], spt_max[i + (1 << (j - 1))][j - 1]);
}
}
stack<int>stk;
for(int i = 1; i <= n; stk.push(i++)){
while(!stk.empty() && h[i] < h[stk.top()]){
stk.pop();
}
l_min[i] = (stk.empty() ? 0 : stk.top());
}
while(!stk.empty()){
stk.pop();
}
for(int i = n; i > 0; stk.push(i--)){
while(!stk.empty() && h[i] < h[stk.top()]){
stk.pop();
}
r_min[i] = (stk.empty() ? n + 1 : stk.top());
}
for(int i = 1; i <= n; i++){
a.emplace_back(min(l_min[i] == 0 ? INF : get_max(l_min[i] + 1, i), r_min[i] == n + 1 ? INF : get_max(i, r_min[i] - 1)) - h[i], i);
}
sort(a.begin(), a.end(), greater<pair<int, int>>());
st.assign(n + 1, Node());
build();
build_dif();
for(int i = 1; i <= n; i++){
st[i] = st[i - 1];
update(i, a[i].second);
}
}
int get(int id, int u, int v, int l = 1, int r = n){
if(l > v || r < u){
return 0;
}
if(u <= l && v >= r){
return st[id].cnt;
}
int m = (l + r) >> 1;
return get(st[id].l, u, v, l, m) + get(st[id].r, u, v, m + 1, r);
}
int max_towers(int l, int r, int d){
int low = 1, high = n, id = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(a[mid].first >= d){
low = (id = mid) + 1;
}
else{
high = mid - 1;
}
}
int sum = get(id, ++l, ++r);
if(sum < 2){
return 1 + int(get_dif(l, r) >= d);
}
low = l;
high = r;
int L, R;
while(low <= high){
int mid = (low + high) >> 1;
if(get(id, l, mid) > 0){
high = (L = mid) - 1;
}
else{
low = mid + 1;
}
}
low = l;
high = r;
while(low <= high){
int mid = (low + high) >> 1;
if(get(id, mid, r) > 0){
low = (R = mid) + 1;
}
else{
high = mid - 1;
}
}
int pl = 0, pr = n + (low = 1);
high = L;
while(low <= high){
int mid = (low + high) >> 1;
if(get_max(mid, L) - d >= h[L]){
low = (pl = mid) + 1;
}
else{
high = mid - 1;
}
}
low = R;
high = n;
while(low <= high){
int mid = (low + high) >> 1;
if(get_max(R, mid) - d >= h[R]){
high = (pr = mid) - 1;
}
else{
low = mid + 1;
}
}
return sum + int(get_dif(l, pl) >= d) + int(get_dif(pr, r) >= d);
}
