#include <bits/stdc++.h>
#include "towers.h"
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10 , inf = 1e9 , Lg = 17;
int n , a[N] , rmxq[N][Lg] , rmnq[N][Lg] , lg2[N] , nexL[N] , nexR[N] , las;
int b[N] , psum[N] , m;
vector <int> all;
vector <pair<int , int>> good;
int mn_pos(int aa , int bb)
{
if(a[aa] < a[bb])
return aa;
return bb;
}
int mx_pos(int aa , int bb)
{
if(a[aa] > a[bb])
return aa;
return bb;
}
int Get_mx(int l , int r)
{
r++;
int sz = (r - l); sz = lg2[sz];
return mx_pos(rmxq[l][sz] , rmxq[r - (1 << sz)][sz]);
}
int Get_mn(int l , int r)
{
r++;
int sz = (r - l); sz = lg2[sz];
return mn_pos(rmnq[l][sz] , rmnq[r - (1 << sz)][sz]);
}
void Build()
{
lg2[1] = 0;
for(int i = 2 ; i < N ; i++)
lg2[i] = lg2[i / 2] + 1;
for(int i = 0 ; i < n ; i++)
rmnq[i][0] = rmxq[i][0] = i;
for(int j = 1 ; j < Lg ; j++)
{
int len = (1 << j);
for(int i = 0 ; i + len <= n ; i++)
{
rmnq[i][j] = mn_pos(rmnq[i][j - 1] , rmnq[i + len / 2][j - 1]);
rmxq[i][j] = mx_pos(rmxq[i][j - 1] , rmxq[i + len / 2][j - 1]);
}
}
for(int i = 1 ; i + 1 < n ; i++) if(a[i] > a[i - 1] && a[i] > a[i + 1])
b[i] = 1;
for(int i = 1 ; i < n ; i++)
psum[i] = psum[i - 1] + b[i];
vector <int> st;
for(int i = 0 ; i < n ; i++)
{
nexL[i] = -1;
nexR[i] = n;
while(!st.empty())
{
if(a[st.back()] < a[i])
{
nexR[st.back()] = i;
st.pop_back();
}
else
{
nexL[i] = st.back();
break;
}
}
st.push_back(i);
}
for(int i = 0 ; i < n ; i++) if(i - nexL[i] > 1 && nexR[i] - i > 1)
{
int lc = Get_mn(nexL[i] + 1 , i - 1) , rc = Get_mn(i + 1 , nexR[i] - 1);
all.push_back(a[i] - max(a[lc] , a[rc]));
}
sort(all.begin() , all.end());
}
void init(int nn , vector <int> vec)
{
n = nn;
for(int i = 0 ; i < n ; i++)
a[i] = vec[i];
Build();
}
int Solve(int l , int r , int d)
{
if(l > r)
return 0;
int pos_mx = Get_mx(l , r);
int res = Solve(l , pos_mx - 1 , d) + Solve(pos_mx + 1 , r , d);
if(pos_mx != l && pos_mx != r)
{
int lc = Get_mn(l , pos_mx - 1) , rc = Get_mn(pos_mx + 1 , r);
if(a[pos_mx] - a[lc] >= d && a[pos_mx] - a[rc] >= d)
res++;
}
return res;
}
struct SEG
{
vector <int> t[N << 2];
int mx[N << 2] , mn[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = m)
{
if(nr - nl == 1)
{
t[node].push_back(good[nl].F);
mx[node] = good[nl].S;
mn[node] = good[nl].S;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid); Build(rc , mid , nr);
t[node] = t[lc];
for(auto u : t[rc])
t[node].push_back(u);
sort(t[node].begin() , t[node].end());
mx[node] = max(mx[lc] , mx[rc]);
mn[node] = min(mn[lc] , mn[rc]);
}
int Get(int l , int r , int node = 1 , int nl = 0 , int nr = m)
{
if(mx[node] <= r)
{
int id = lower_bound(t[node].begin() , t[node].end() , l) - t[node].begin();
return t[node].size() - id;
}
if(mn[node] > r)
return 0;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
return Get(l , r , lc , nl , mid) + Get(l , r , rc , mid , nr);
}
} seg;
void Prep(int d)
{
for(int i = 0 ; i < n ; i++) if(i - nexL[i] > 1 && nexR[i] - i > 1)
{
int lc = Get_mn(nexL[i] + 1 , i - 1) , rc = Get_mn(i + 1 , nexR[i] - 1);
int mx_d = a[i] - max(a[lc] , a[rc]);
if(d > mx_d)
continue;
int low = nexL[i] + 1 , high = i;
while(high - low > 1)
{
int mid = (low + high) >> 1;
lc = Get_mn(mid , i - 1);
if(a[i] - a[lc] >= d)
low = mid;
else
high = mid;
}
int L = low;
low = i; high = nexR[i] - 1;
while(high - low > 1)
{
int mid = (low + high) >> 1;
rc = Get_mn(i + 1 , mid);
if(a[i] - a[rc] >= d)
high = mid;
else
low = mid;
}
int R = high;
good.push_back({L , R});
}
m = good.size();
seg.Build();
}
int max_towers(int l , int r , int d)
{
if(d == 1)
{
if(l + 1 >= r)
return 1;
return 1 + psum[r - 1] - psum[l];
}
if(psum[r - 1] - psum[l] == 0)
return 1;
if(psum[r - 1] - psum[l] == 1)
{
int id = Get_mx(l , r);
int lc = Get_mn(l , id - 1) , rc = Get_mn(id + 1 , r);
if(a[id] - d >= a[lc] && a[id] - d >= a[rc])
return 2;
return 1;
}
if(l == 0 && r == n - 1)
{
int id = lower_bound(all.begin() , all.end() , d) - all.begin();
return all.size() - id + 1;
}
if(las == 0)
{
Prep(d);
las = d;
}
if(las == d)
{
return seg.Get(l , r) + 1;
}
return 1 + Solve(l , r , d);
}
