#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int L = 22;
int n, a[N], pl[N], pr[N], ord[N], go_l[N], go_r[N];
bool cmp(int i, int j) { return a[i] < a[j]; }
int mx[N][L], logs[N];
int qmx(int l, int r) {
if (l > r) return (int) -1e9;
int k = logs[r - l + 1];
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void buildST() {
for (int i = 1; i <= n; i++) mx[i][0] = a[i];
for (int i = 2; i <= n; i++) logs[i] = logs[i >> 1] + 1;
for (int j = 1; j < L; j++)
for (int i = 1; i + (1 << j) <= n + 1; i++)
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
const int M = N * L;
int tsz, ls[M], rs[M], sum[M];
void modify(int& v, int p, int tl, int tr, int i, int x) {
v = ++tsz;
ls[v] = ls[p];
rs[v] = rs[p];
sum[v] = sum[p] + x;
if (tl == tr) {
return;
}
int mid = tl + tr >> 1;
if (i <= mid) {
modify(ls[v], ls[p], tl, mid, i, x);
} else {
modify(rs[v], rs[p], mid + 1, tr, i, x);
}
}
int query(int v, int tl, int tr, int ql, int qr) {
if (tl > tr || tl > qr || tr < ql) {
return 0;
}
if (ql <= tl && tr <= qr) {
return sum[v];
}
int mid = tl + tr >> 1;
return query(ls[v], tl, mid, ql, qr) + query(rs[v], mid + 1, tr, ql, qr);
}
int find_first(int v, int tl, int tr, int p) {
if (tr < p || !sum[v]) {
return n + 1;
}
if (tl == tr) {
return sum[v] > 0 ? tl : n + 1;
}
int mid = tl + tr >> 1;
int ans_l = find_first(ls[v], tl, mid, p);
if (ans_l == n + 1)
return find_first(rs[v], mid + 1, tr, p);
else
return ans_l;
}
int find_last(int v, int tl, int tr, int p) {
if (tl > p || !sum[v]) {
return 0;
}
if (tl == tr) {
return sum[v] > 0 ? tl : 0;
}
int mid = tl + tr >> 1;
int ans_r = find_last(ls[v], mid + 1, tr, p);
if (ans_r == 0)
return find_last(ls[v], tl, mid, p);
else
return ans_r;
}
struct node {
int mn, mx, l_diff, r_diff;
};
node comb(node nl, node nr) {
node res;
res.mn = min(nl.mn, nr.mn);
res.mx = max(nl.mx, nr.mx);
res.l_diff = max({nl.l_diff, nr.l_diff, nr.mx - nl.mn});
res.r_diff = max({nl.r_diff, nr.r_diff, nl.mx - nr.mn});
return res;
}
namespace segtree {
node st[8 * N];
void build(int v, int tl, int tr) {
if (tl == tr) {
st[v].mn = a[tl];
st[v].mx = a[tl];
st[v].l_diff = 0;
st[v].r_diff = 0;
return;
}
int mid = tl + tr >> 1;
build(v * 2, tl, mid);
build(v * 2 + 1, mid + 1, tr);
st[v] = comb(st[v * 2], st[v * 2 + 1]);
}
node query(int v, int tl, int tr, int ql, int qr) {
if (tl > tr || tl > qr || tr < ql) {
assert(false);
}
if (ql <= tl && tr <= qr) {
return st[v];
}
int mid = tl + tr >> 1;
if (qr <= mid) {
return query(v * 2, tl, mid, ql, qr);
} else if (ql > mid) {
return query(v * 2 + 1, mid + 1, tr, ql, qr);
} else {
return comb(query(v * 2, tl, mid, ql, qr), query(v * 2 + 1, mid + 1, tr, ql, qr));
}
}
};
vector<pair<int, int>> qs;
vector<int> roots;
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = H[i - 1];
}
segtree::build(1, 1, n);
go_r[1] = 1;
for (int i = 2; i <= n; i++) {
go_r[i] = (a[i - 1] < a[i] ? go_r[i - 1] : i);
}
go_l[n] = n;
for (int i = n - 1; i >= 1; i--) {
go_l[i] = (a[i + 1] < a[i] ? go_l[i + 1] : i);
}
vector <int> stk;
for (int i = 1; i <= n; i++) {
while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
pl[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
stk.clear();
for (int i = n; i >= 1; i--) {
while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
pr[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
buildST();
for (int i = 1; i <= n; i++) ord[i] = i;
sort(ord + 1, ord + n + 1, cmp);
for (int _i = 2; _i <= n; _i++) {
int i = ord[_i];
int D = 1.001e9;
if (pl[i] != -1) D = min(D, qmx(pl[i] + 1, i) - a[i]);
if (pr[i] != -1) D = min(D, qmx(i, pr[i] - 1) - a[i]);
qs.emplace_back(D, i);
}
sort(qs.begin(), qs.end());
roots.push_back(0);
modify(roots.back(), roots.back(), 1, n, ord[1], 1);
int sz = (int) qs.size();
for (int i = sz - 1; i >= 0; i--) {
int prv = (int) roots.back();
roots.push_back(0);
modify(roots.back(), prv, 1, n, qs[i].second, 1);
}
reverse(roots.begin(), roots.end());
}
int get_pos(int d) {
int low = 0, high = (int) qs.size() - 1, res = high + 1;
while (low <= high) {
int mid = low + high >> 1;
if (qs[mid].first >= d) {
res = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return res;
}
int find_first_bs(int rt, int p) {
int low = p, high = n, res = n;
while (low <= high) {
int mid = low + high >> 1;
if (query(rt, 1, n, p, mid) > 0) {
res = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return res;
}
int find_last_bs(int rt, int p) {
int low = 1, high = p, res = 1;
while (low <= high) {
int mid = low + high >> 1;
if (query(rt, 1, n, mid, p) > 0) {
res = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return res;
}
int max_towers(int L, int R, int D) {
if (L == R) {
return 1;
}
++L; ++R;
int p = get_pos(D);
int ans = query(roots[p], 1, n, L, R);
if (ans == 0) {
int fl = go_l[L];
//while (fl + 1 <= R && a[fl] > a[fl + 1]) fl++;
int fr = go_r[R];
// while (fr - 1 >= L && a[fr - 1] < a[fr]) fr--;
if (fl >= fr) {
return 1;
}
return (max(a[fl], a[fr]) <= qmx(fl, fr) - D) ? 2 : 1;
}
int l = find_first_bs(roots[p], L);
int r = find_last_bs(roots[p], R);
if (L < l) {
int low = L, high = l - 1, pos = l;
while (low <= high) {
int mid = low + high >> 1;
if (qmx(mid, l - 1) >= a[l] + D) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != l && segtree::query(1, 1, n, L, pos).l_diff >= D) {
ans += 1;
}
}
if (r < R) {
int low = r + 1, high = R, pos = r;
while (low <= high) {
int mid = low + high >> 1;
if (qmx(r + 1, mid) >= a[r] + D) {
pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
if (pos != r && segtree::query(1, 1, n, pos, R).r_diff >= D) {
ans += 1;
}
}
// for (int i = L; i < l; i++) {
// if (max(a[i], a[l]) <= qmx(i, l) - D) {
// ans += 1;
// break;
// }
// }
// for (int i = R; i > r; i--) {
// if (max(a[r], a[i]) <= qmx(r, i) - D) {
// ans += 1;
// break;
// }
// }
return ans;
}
/*
7 3
10 20 60 40 50 30 70
1 5 10
2 2 100
0 6 17
3
1
2
*/
