// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "towers.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#ifdef DEBUG
auto &operator<<(auto &os, const pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto &operator<<(auto &os, const auto &v) {
os << "{";
for(auto it=begin(v);it!=end(v);it++) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif
int count_larger(const vi &vec, int x) {
dbg(vec);
int b = 0, e = sz(vec);
while(b < e) {
int mid = (b+e) / 2;
if(vec[mid] < x) b = mid + 1;
else e = mid;
}
return sz(vec) - b;
}
struct SegTree {
int n;
vector<vi> tree;
SegTree() {}
SegTree(vi vals) {
n = 1;
while(n < sz(vals))
n *= 2;
tree.assign(2*n, {});
rep(i,0,n)
if(i < sz(vals))
tree[n+i] = {vals[i]};
else
tree[n+i] = {-1};
dbg(tree);
for(int i=n-1;i>0;i--)
merge(all(tree[2*i]), all(tree[2*i+1]), back_inserter(tree[i]));
dbg(tree);
}
int query(int l, int r, int x) {
int res = 0;
for(l+=n, r+=n; l<r; l/=2, r/=2) {
if(l&1) res += count_larger(tree[l++], x);
if(r&1) res += count_larger(tree[--r], x);
}
return res;
}
};
const int inf = 2e9 + 7;
int n;
vi h;
vi sel;
vi tim;
vi lft, rht;
SegTree *tree;
void init(int N, vi H) {
n = N;
h = H;
sel.assign(n, 0);
int prev = -1;
bool small = false;
rep(i,0,n) {
if(small) {
if(prev != -1 && h[i] <= h[prev]) {
sel[prev] = false;
sel[i] = true;
prev = i;
}
else {
prev = i;
sel[i] = true;
small = false;
}
} else {
if(prev != -1 && h[i] >= h[prev]) {
sel[prev] = false;
sel[i] = true;
prev = i;
}
else {
prev = i;
sel[i] = true;
small = true;
}
}
}
dbg(sel);
set<pii> s;
tim.assign(n, -1);
lft.assign(n, -1);
rht.assign(n, -1);
prev = -1;
rep(i,0,n) {
if(!sel[i])
continue;
lft[i] = prev;
if(prev != -1) rht[prev] = i;
prev = i;
}
auto distance = [&](const int a, const int b) {
return (int)abs(h[a] - h[b]);
};
auto update = [&](const int i) {
s.erase({tim[i], i});
tim[i] = inf;
if(lft[i] != -1) tim[i] = min(tim[i], distance(i, lft[i]));
if(rht[i] != -1 && rht[rht[i]] != -1) tim[i] = min(tim[i], distance(i, rht[i]));
s.insert({tim[i], i});
};
int parity = 1;
rep(i,0,n) {
if(!sel[i])
continue;
if(parity) update(i);
parity ^= 1;
}
while(sz(s)) {
auto [t, i] = *s.begin();
s.erase(s.begin());
dbg(t, i);
if(lft[i] != -1 && t == distance(i, lft[i]) && lft[lft[i]] != -1) {
rht[lft[lft[i]]] = rht[i];
update(lft[lft[i]]);
}
if(rht[i] != -1 && t == distance(i, rht[i]) && rht[rht[i]] != -1) {
lft[rht[rht[i]]] = lft[i];
update(rht[rht[i]]);
}
dbg(tim);
}
tree = new SegTree(tim);
}
int max_towers(int L, int R, int D) {
int num = tree->query(0, n, D);
if(num == 0) return 1;
dbg(D, num);
return num;
// return (num + 1) / 2;
}
