#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
vector<int> V;
int a[mxn], n, T[mxn][20];
int query(int l, int r) {
int k = __lg(r - l + 1);
return max( T[l][k], T[r-(1<<k)+1][k] );
}
void init(int _n, vector<int> H) {
n = _n;
for(int i=0; i<n; i++) {
a[i] = H[i];
T[i][0] = a[i];
}
for(int j=1; j<20; j++)
for(int i=0; i+(1<<j)-1<n; i++)
T[i][j] = max( T[i][j-1], T[i+(1<<(j-1))][j-1] );
vector<int> L(n, -1), R(n, n);
stack<int> st;
for(int i=0; i<n; i++) {
while(!st.empty() && a[st.top()] >= a[i]) st.pop();
if(!st.empty()) L[i] = st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=n-1; i>=0; i--) {
while(!st.empty() && a[st.top()] >= a[i]) st.pop();
if(!st.empty()) R[i] = st.top();
st.push(i);
}
for(int i=0; i<n; i++) {
if(L[i] == i-1 && R[i] == i+1) {
V.push_back(-1e9);
continue;
}
int mx = 1e9;
if(L[i] != i-1) mx = min(mx, query(L[i]+1, i-1));
if(R[i] != i+1) mx = min(mx, query(i+1, R[i]-1));
V.push_back(mx);
}
sort(V.begin(), V.end());
}
int max_towers(int L, int R, int D) {
int l=0, r=n-1, p=n-1;
while(l <= r) {
int mid = (l + r) / 2;
if(V[mid] >= D) p = mid, r = mid - 1;
else l = mid + 1;
}
return n-p;
}
