//lurker you should listen to https://www.youtube.com/watch?v=a3egbaw-VK4 ASAP
//Hofstadter's law: programming projects take longer than you expect, even when you take into account Hofstadter's law
#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
const int MX = 1e5+5;
const int INF = 2e9;
const int LOGM = 18;
int n;
vector<int> a(MX);
vector<int> lo_w(MX);
vector<int> hi_w(MX);
vector<int> nxt_lo(MX);//next optimal descent.
vector<int> nxt_hi(MX);//next optimal ascent.
vector<int> clow(MX);
int LO[LOGM][MX];
int HI[LOGM][MX];
int Nxt[LOGM][MX];
bool rinited = false;
void init(int N, vector<int> h)
{
n = N;
rinited = false;
for(int i = 1; i <= n; i++)
a[i] = h[i-1];
vector<int> lo(n+2);//immediate next dip
vector<int> hi(n+2);//immediate next up
//vector<int> lo_w(n+1);//suppose a[i], >a[i], >a[i] ..., < a[i]. largest "value" among the next few vals
//vector<int> hi_w(n+1);//same as above, smallest value among the next few vals
for(int i = 1; i <= n; i++)
lo[i] = hi[i] = i+1;
a[n+1] = -INF; LO[0][n] = LO[0][n+1] = n+1;
for(int i = n; i >= 1; i--)
{
lo_w[i] = a[i];
while(a[lo[i]] > a[i])
{
lo_w[i] = max(lo_w[i], lo_w[lo[i]]);
lo[i] = lo[lo[i]];
}
LO[0][i] = lo[i];
}
a[n+1] = +INF; HI[0][n] = HI[0][n+1] = n+1;
for(int i = n; i >= 1; i--)
{
hi_w[i] = a[i];
while(a[hi[i]] < a[i])
{
hi_w[i] = min(hi_w[i], hi_w[hi[i]]);
hi[i] = hi[hi[i]];
}
HI[0][i] = hi[i];
}
for(int i = 1; i <= n; i++)
{
lo_w[i] = lo_w[i] - a[i];
hi_w[i] = a[i] - hi_w[i];
}
for(int k = 1; k < LOGM; k++)
{
for(int i = 1; i <= n+1; i++)
LO[k][i] = LO[k-1][LO[k-1][i]];
for(int i = 1; i <= n+1; i++)
HI[k][i] = HI[k-1][HI[k-1][i]];
}
/*cout << "Debugging vals: " << endl;
for(int i = 1; i <= n; i++)
cout << lo_w[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << hi_w[i] << " ";
cout << endl;*/
return;
}
void r_init(int D)
{
if(rinited)
return;
rinited = true;
vector<int> sp_lo(n+2, n+1);
vector<int> sp_hi(n+2, n+1);
clow.assign(n+2, n+1);
for(int i = n; i >= 1; i--)
{
if(lo_w[i] >= D)
sp_lo[i] = i;
else
sp_lo[i] = sp_lo[LO[0][i]];
clow[i] = sp_lo[i];
if(hi_w[i] >= D)
sp_hi[i] = i;
else
sp_hi[i] = sp_hi[HI[0][i]];
}
for(int i = 1; i <= n; i++)
{
//cout << "Currently computing optimal jumps for i = " << i << endl;
int u = i;
a[n+1] = INF;
for(int k = LOGM-1; k >= 0; k--)
{
if(a[HI[k][u]] < (D+a[i]))
u = HI[k][u];
}
u = HI[0][u];
//cout << "First worker = " << u << endl;
//now u is the smallest active fellow after i.
int j = sp_hi[u];
//cout << "- First jump should go to " << j << endl;
if(j == (n+1))
{
Nxt[0][i] = n+1;
continue;
}
a[n+1] = -INF;
u = j;
for(int k = LOGM-1; k >= 0; k--)
{
if(a[LO[k][u]] > (a[j]-D))
u = LO[k][u];
}
u = LO[0][u];
//cout << "Ended at " << u << endl;
int ip = sp_lo[u];
Nxt[0][i] = ip;
if((ip) == (n+1))
Nxt[0][i] = u;
//cout << "--- Next jump should go to " << Nxt[0][i] << endl;
}
Nxt[0][n+1] = n+1;
for(int k = 1; k < LOGM; k++)
{
for(int i = 1; i <= (n+1); i++)
{
Nxt[k][i] = Nxt[k-1][Nxt[k-1][i]];
//cout << Nxt[k][i] << " ";
}
//cout << endl;
}
return;
}
int max_towers(int L, int R, int D)
{
L++; R++;
r_init(D);
if(clow[L] > R)
return 1;
int ans = 1;
int u = clow[L];
//cout << "For optimal results, we should start at u = " << u << endl;
for(int k = LOGM-1; k >= 0; k--)
{
if(Nxt[k][u] <= R)
{
u = Nxt[k][u];
//cout << "I jumped to " << u << endl;
ans+=((1ll<<k));
}
}
return ans;
}
