#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int INF = 1e9;
int n;
vi H;
vi St, Dr;
vi DeltaSt, DeltaDr;
struct RMQ {
int n;
vector<vi> A;
RMQ(vi V0) : n((int)V0.size()) {
A.push_back(V0);
for(int k = 1; (1 << k) <= n; ++k) {
A.push_back(A.back());
for(int i = 0; i < n; ++i) {
if(i + (1 << (k - 1)) < n)
A[k][i] = max(A[k][i], A[k - 1][i + (1 << (k - 1))]);
}
}
}
int query(int l, int r) {
int d = 31 - __builtin_clz(r - l + 1);
return max(A[d][l], A[d][r - (1 << d) + 1]);
}
};
pair<vi, vi> descomp(vi A) {
RMQ R(A);
vi Ant(n, -1);
vi Delta(n, INF); /// cel mai mare delta posibil
stack<int> S;
for(int i = 0; i < n; ++i) {
while(!S.empty() && A[S.top()] > A[i]) {
S.pop();
}
if(!S.empty()) {
Ant[i] = S.top();
Delta[i] = R.query(S.top(), i) - A[i];
}
S.push(i);
}
return make_pair(Ant, Delta);
}
vi S;
void init(int N0, vi H0) {
n = N0;
H = H0;
tie(St, DeltaSt) = descomp(H);
reverse(H.begin(), H.end());
tie(Dr, DeltaDr) = descomp(H);
reverse(H.begin(), H.end());
reverse(Dr.begin(), Dr.end());
reverse(DeltaDr.begin(), DeltaDr.end());
for(auto &it : Dr)
it = n - it - 1;
for(int i = 0; i < n; ++i) {
S.push_back(min(DeltaSt[i], DeltaDr[i]));
}
sort(S.begin(), S.end());
// cout << "St: ";
// for(auto it : St) cout << it << " ";
// cout << "\n";
// cout << "DeltaSt: ";
// for(auto it : DeltaSt) cout << it << " ";
// cout << "\n";
// cout << "Dr: ";
// for(auto it : Dr) cout << it << " ";
// cout << "\n";
// cout << "DeltaDr: ";
// for(auto it : DeltaDr) cout << it << " ";
// cout << "\n";
}
int max_towers(int L, int R, int D) {
int v = lower_bound(S.begin(), S.end(), D) - S.begin();
return n - v;
}
