#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;
S.resize(n);
for(int i = 0; i < n; ++i) {
S[i] = min(DeltaSt[i], DeltaDr[i]);
}
// 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) {
vi Sol;
for(int i = l; i <= r; ++i) {
if(S[i] >= D) {
Sol.push_back(i);
}
}
if(Sol.empty()) {
///poate gasim un SolDr >= D si dupa un SolSt >= D
int tip = 0;
for(int i = l; i <= r; ++i) {
if(DeltaDr[i] >= D) {
if(tip == 0) {
tip = 1;
continue;
}
}
if(DeltaSt[i] >= D && tip == 1) {
tip = 2;
continue;
}
}
if(tip == 2) return 2;
return 1;
}
int found_st = 0, found_dr = 0;
for(int i = l; i < Sol[0]; ++i)
if(DeltaDr[i] >= D) found_st = 1;
for(int i = Sol.back() + 1; i <= r; ++i)
if(DeltaSt[i] >= D) found_dr = 1;
return int(Sol.size()) + found_st + found_dr;
}
