#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int seg[400005], order[100005], a[100005], n;
vector<int> h, seglist[400005];
set<int> s;
bool cmp(int x, int y)
{
return h[x]<h[y];
}
void build(int i, int l, int r)
{
if (l==r)
{
if (l==-1 || l==n)
seg[i]=2e9;
else
seg[i]=h[l];
return;
}
int m=(l+r+2)/2-1;
build(i*2, l, m);
build(i*2+1, m+1, r);
seg[i]=max(seg[i*2], seg[i*2+1]);
}
int query(int i, int l, int r, int ql, int qr)
{
if (ql<=l && r<=qr)
return seg[i];
int m=(l+r+2)/2-1, res=0;
if (ql<=m && l<=qr)
res=max(res, query(i*2, l, m, ql, qr));
if (ql<=r && m<qr)
res=max(res, query(i*2+1, m+1, r, ql, qr));
return res;
}
void buildlist(int i, int l, int r)
{
if (l==r)
{
seglist[i].push_back(a[l]);
//cout << i << ' ' << a[l] << '\n';
return;
}
int m=(l+r)/2;
buildlist(i*2, l, m);
buildlist(i*2+1, m+1, r);
for (int x:seglist[i*2])
seglist[i].push_back(x);
for (int x:seglist[i*2+1])
seglist[i].push_back(x);
sort(seglist[i].begin(), seglist[i].end());
}
int querylist(int i, int l, int r, int ql, int qr, int x)
{
if (ql<=l && r<=qr)
{
int ind=lower_bound(seglist[i].begin(), seglist[i].end(), x)-seglist[i].begin();
//cout << l << ' ' << r << ": ";
//for (int x:seglist[i])
// cout << x << ' ';
//cout << " " << ind << '\n';
return seglist[i].size()-ind;
}
int m=(l+r)/2, res=0;
if (ql<=m && l<=qr)
res+=querylist(i*2, l, m, ql, qr, x);
if (ql<=r && m<qr)
res+=querylist(i*2+1, m+1, r, ql, qr, x);
return res;
}
void init(int N, vector<int> H)
{
n=N;
h=H;
build(1, -1, n);
for (int i=0; i<n; i++)
order[i]=i;
sort(order, order+n, cmp);
s.insert(-2);
s.insert(n+1);
for (int i=0; i<n; i++)
{
int ind=order[i];
auto it=s.lower_bound(ind);
int l=*prev(it), r=*it;
int res1=(ind-l==1?0:query(1, -1, n, l+1, ind-1));
int res2=(r-ind==1?0:query(1, -1, n, ind+1, r-1));
a[ind]=min(res1, res2)-h[ind];
s.insert(ind);
}
buildlist(1, 0, n-1);
}
int max_towers(int l, int r, int d)
{
return querylist(1, 0, n-1, l, r, d);
}
