#include "towers.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define NN 100010
#define M 1000000007 // 998244353
ll h[NN];
ll n;
namespace seg {
typedef pl T;
T id={-1, -1};
T f(T a, T b) {return pair(max(a.K, b.K), max(a.V, b.V)) ;}
T t[2 * NN];
ll n=NN; // array size
void init(ll p, ll value) { // set value at position p
for (p+=n, t[p].K = value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
}
void modify(ll p, ll value) { // set value at position p
for (p+=n, t[p].V = max(t[p].V, value); p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
}
T query(ll l, ll r) { // fold f on interval [l, r)
T resl=id, resr=id;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) resl = f(resl, t[l++]);
if (r&1) resr = f(t[--r], resr);
}
return f(resl, resr);
}
}
vector<pl> segs;
void init(int N, std::vector<int> H) {
n = N;
F(i, 0, n) h[i] = H[i];
F(i, 0, n) seg::init(i, H[i]);
F(i, 0, n-1) if (h[i] < h[i+1]) {
if (segs.size() and segs.back().V == i - 1) segs.back().V = i;
else segs.emplace_back(i, i);
}
}
/*
4 1 2 3 5 1 2 3
[ ] [ ]
*/
int solved1(ll L, ll R) {
if (L == R) return 1;
ll extra = 0;
if (h[R-1] > h[R]) extra++;
ll ans = 0;
auto it = upper_bound(A(segs), pl(L, -1));
if (it != segs.begin()) --it;
ans = lower_bound(A(segs), pl(R, -1)) - it;
auto nxt = lower_bound(A(segs), pl(R, -1));
if (nxt != segs.end() and nxt->K <= R and R <= nxt->V and extra) extra--;
return ans + extra;
}
int brute(int L, int R, int D) {
F(i, 0, 2*NN) seg::t[i].V = -1;
ll res = 0;
// ll res2 = 0;
F(i, L, R+1) {
ll ans = 1;
// ll ans2 = 1;
{
// for (ll cur = i-1; cur >= L; cur--) if (h[cur] >= D + h[i]) ans2 = max(ans2, dp[cur] + 1);
ll l = L - 1, r = i + 1;
while (l+1<r) {
ll m = (l+r)/2;
if (seg::query(m, i).K >= D + h[i]) l = m;
else r = m;
}
// if (i == 5) {
// cout << L << " " << l+1 << " " << seg::query(L, l+1).V << " " << endl;
// cout << seg::query(l, l+1).V << endl;
// }
ans = max(ans, seg::query(L, l+1).V + 1);
}
{
// for (ll cur = i+1; cur <= R; cur++) if (h[cur] >= D + h[i]) dp[cur] = max(dp[cur], ans2);
ll l = i, r = R+1;
while (l+1<r) {
ll m = (l+r)/2;
if (seg::query(i, m+1).K >= D + h[i]) r = m;
else l = m;
}
seg::modify(r, ans);
// if (ans2 == 3) cout << "TURNEd 3 AT " << i << endl;
}
res = max(res, ans);
// res2 = max(ans, ans2);
// cout << "ARRAYS FOR " << i << endl;
// F(i, L, R+1) cout << dp[i] << " "; cout << endl;
// F(i, L, R+1) cout << seg::query(i, i+1).V << " "; cout << endl;
}
// assert(res == res2);
return res;
}
int max_towers(int L, int R, int D) {
static int calls = 0;
if (calls++ > 1)
{
// we are in special cases
if (D == 1) {
int ans = solved1(L, R);
// int rans = brute(L, R, D);
// cout << "QUERYING " << L << " " << R << endl;
// cout << "WTF " << ans << " " << rans << endl;
// cout << "YO?? IDEMPOTENCY<???? " << brute(L, R, D) << " " << brute(L, R, D) << endl;
// assert(ans == rans);
return ans;
}
assert(false);
return -1;
}
// vl dp(n+1, -1);/
return brute(L, R, D);
}
