#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;
const int MN = 100000;
struct AIB2D {
int n;
vi V[4 * MN];
AIB2D() {}
AIB2D(const vi &V0) : n((int)V0.size()) {
build(V0, 1, 0, n - 1);
}
void build(const vi &V0, int u, int s, int d) {
for(int i = s; i <= d; ++i)
V[u].push_back(V0[i]);
sort(V[u].begin(), V[u].end());
if(s != d) {
build(V0, u << 1, s, (s + d) >> 1);
build(V0, u << 1 | 1, ((s + d) >> 1) + 1, d);
}
}
int query(int l, int r, int D, int u, int s, int d) {
if(d < l || r < s) return 0;
if(l <= s && d <= r) {
int v = lower_bound(V[u].begin(), V[u].end(), D) - V[u].begin();
return int(V[u].size()) - v;
}
return query(l, r, D, u << 1, s, (s + d) >> 1)
+ query(l, r, D, u << 1 | 1, ((s + d) >> 1) + 1, d);
}
int query(int l, int r, int D) {
return query(l, r, D, 1, 0, n - 1);
}
};
AIB2D ASt, ADr;
AIB2D ATot;
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]);
ASt = AIB2D(DeltaSt);
ADr = AIB2D(DeltaDr);
ATot = AIB2D(S);
}
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(ATot.query(l, r, D) == 0) {
///poate gasim un SolDr >= D si dupa un SolSt >= D
int st = l, dr = r, mij;
if(ADr.query(l, r, D) == 0) return 1;
while(st < dr) {
mij = (st + dr) / 2;
if(ADr.query(l, r, D)) dr = mij;
else st = mij + 1;
}
if(ASt.query(st + 1, r, D)) return 2;
return 1;
}
int st, dr, mij;
int p1;
st = l, dr = r;
while(st < dr) {
mij = (st + dr) / 2;
if(ATot.query(l, mij, D)) dr = mij;
else st = mij + 1;
}
p1 = st;
int p2;
st = l; dr = r;
while(st < dr) {
mij = (st + dr + 1) / 2;
if(ATot.query(mij, r, D)) st = mij;
else dr = mij - 1;
}
p2 = st;
int found_st = 0, found_dr = 0;
found_st = !!ADr.query(l, p1 - 1, D);
found_dr = !!ASt.query(p2 + 1, r, D);
return int(Sol.size()) + found_st + found_dr;
}
