#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<17;
int drz[2 * N], drz2[2 * N], drz3[2 * N], drz4[2 * N];
int drzmi[2 * N], drzma[2 * N];
vector<int> mrg[2 * N];
int tab[N], ml[N], mr[N], cdi[N], tim[N];
set<int> cur;
set<int>::iterator it;
set<pair<int, int>> dif;
int FindL(int v, int a, int b, int pz, int kz, int x)
{
if(a > kz || b < pz || drzma[v] < x) return N;
if(v >= N) return v - N;
int ans = FindL(v * 2, a, (a + b) / 2, pz, kz, x);
if(ans < N) return ans;
ans = FindL(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz, x);
return ans;
}
int FindR(int v, int a, int b, int pz, int kz, int x)
{
if(a > kz || b < pz || drzma[v] < x) return 0;
if(v >= N) return v - N;
int ans = FindR(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz, x);
if(ans != 0) return ans;
ans = FindR(v * 2, a, (a + b) / 2, pz, kz, x);
return ans;
}
int FindXD(int a, int b, int k)
{
vector<int> x, y;
a += N - 1; b += N + 1;
while(a / 2 != b / 2)
{
if(a % 2 == 0) x.pb(a + 1);
if(b % 2 == 1) y.pb(b - 1);
a /= 2; b /= 2;
}
reverse(y.begin(), y.end());
for(int j = 0; j < (int)y.size(); ++j) x.pb(y[j]);
int curmi = II;
for(int i = 0; i < (int)x.size(); ++i)
{
if(drz3[x[i]] >= k || drz[x[i]] - curmi >= k)
{
int v = x[i];
while(v < N)
{
v *= 2;
if(!(drz3[v] >= k || drz[v] - curmi >= k))
{
curmi = min(curmi, drz2[v]);
++v;
}
}
return v - N;
}
curmi = min(curmi, drz2[x[i]]);
}
return -1;
}
int FindXD2(int a, int b, int k)
{
vector<int> x, y;
a += N - 1; b += N + 1;
while(a / 2 != b / 2)
{
if(a % 2 == 0) x.pb(a + 1);
if(b % 2 == 1) y.pb(b - 1);
a /= 2; b /= 2;
}
reverse(y.begin(), y.end());
for(int j = 0; j < (int)y.size(); ++j) x.pb(y[j]);
reverse(x.begin(), x.end());
int curmi = II;
for(int i = 0; i < (int)x.size(); ++i)
{
if(drz4[x[i]] >= k || drz[x[i]] - curmi >= k)
{
int v = x[i];
while(v < N)
{
v = v * 2 + 1;
if(!(drz4[v] >= k || drz[v] - curmi >= k))
{
curmi = min(curmi, drz2[v]);
--v;
}
}
return v - N;
}
curmi = min(curmi, drz2[x[i]]);
}
return -1;
}
bool ChkL(int a, int b, int k)
{
//cerr << "Chkl: " << a << " " << b << "\n";
vector<int> x, y;
a += N - 1; b += N + 1;
while(a / 2 != b / 2)
{
if(a % 2 == 0) x.pb(a + 1);
if(b % 2 == 1) y.pb(b - 1);
a /= 2; b /= 2;
}
reverse(y.begin(), y.end());
for(int j = 0; j < (int)y.size(); ++j) x.pb(y[j]);
int curmi = II;
for(int i = 0; i < (int)x.size(); ++i)
{
if(drz3[x[i]] >= k) return true;
if(drz[x[i]] - curmi >= k) return true;
curmi = min(curmi, drz2[x[i]]);
}
return false;
}
bool ChkR(int a, int b, int k)
{
vector<int> x, y;
a += N - 1; b += N + 1;
while(a / 2 != b / 2)
{
if(a % 2 == 0) x.pb(a + 1);
if(b % 2 == 1) y.pb(b - 1);
a /= 2; b /= 2;
}
reverse(y.begin(), y.end());
for(int j = 0; j < (int)y.size(); ++j) x.pb(y[j]);
int curma = 0;
for(int i = 0; i < (int)x.size(); ++i)
{
if(drz4[x[i]] >= k) return true;
if(curma - drz2[x[i]] >= k) return true;
curma = max(curma, drz[x[i]]);
}
return false;
}
void DoT(int n)
{
drz2[N] = II; drzmi[N] = II;
for(int i = N; i < 2 * N; ++i)
{
drz3[i] = -II / 2;
drz4[i] = -II / 2;
}
for(int i = 1; i <= n; ++i)
{
drzmi[i + N] = tim[i]; drzma[i + N] = tim[i];
drz[i + N] = tab[i]; drz2[i + N] = tab[i];
mrg[i + N] = {tim[i]};
}
for(int i = n + 1; i < N; ++i)
{drzmi[i + N] = II; drz2[i + N] = II;}
for(int i = N - 1; i >= 1; --i)
{
drzma[i] = max(drzma[2 * i], drzma[2 * i + 1]);
drzmi[i] = min(drzmi[2 * i], drzmi[2 * i + 1]);
drz[i] = max(drz[2 * i], drz[2 * i + 1]);
drz2[i] = min(drz2[2 * i], drz2[2 * i + 1]);
drz3[i] = max(drz3[i * 2], drz3[i * 2 + 1]);
drz3[i] = max(drz3[i], drz[i * 2 + 1] - drz2[i * 2]);
drz4[i] = max(drz4[i * 2], drz4[i * 2 + 1]);
drz4[i] = max(drz4[i], drz[i * 2] - drz2[i * 2 + 1]);
mrg[i] = mrg[i * 2];
for(int j = 0; j < (int)mrg[i * 2 + 1].size(); ++j)
mrg[i].pb(mrg[i * 2 + 1][j]);
sort(mrg[i].begin(), mrg[i].end());
}
}
inline int Il(int v, int x)
{
return (mrg[v].end() - lower_bound(mrg[v].begin(), mrg[v].end(), x));
}
int Query(int a, int b, int x)
{
a += N - 1; b += N + 1;
int ans = 0;
while(a / 2 != b / 2)
{
if(a % 2 == 0) ans += Il(a + 1, x);
if(b % 2 == 1) ans += Il(b - 1, x);
a /= 2; b /= 2;
}
return ans;
}
int GetL(int v)
{
it = cur.lower_bound(v);
if(it == cur.begin()) return 0;
--it; return *it;
}
int GetR(int v)
{
it = cur.upper_bound(v);
if(it == cur.end()) return 0;
return *it;
}
void init(int _N, vector<int> _H)
{
int n = _N;
for(int i = 1; i <= n; ++i) tab[i] = _H[i - 1];
for(int i = 1; i <= n; ++i)
{
ml[i] = 0LL; mr[i] = 0LL;
cur.insert(i);
}
ml[1] = II; mr[n] = II;
for(int i = 1; i <= n; ++i)
{
cdi[i] = min(ml[i], mr[i]) - tab[i];
dif.insert(make_pair(cdi[i], i));
}
while((int)cur.size() > 1)
{
int v = (*dif.begin()).nd;
dif.erase(dif.begin());
cur.erase(v);
tim[v] = cdi[v];
int l = GetL(v), r = GetR(v);
int xd = max(tab[v], max(mr[v], ml[v]));
if(l != 0)
{
dif.erase(make_pair(cdi[l], l));
mr[l] = max(mr[l], xd);
cdi[l] = min(ml[l], mr[l]) - tab[l];
dif.insert(make_pair(cdi[l], l));
}
if(r != 0)
{
dif.erase(make_pair(cdi[r], r));
ml[r] = max(ml[r], xd);
cdi[r] = min(ml[r], mr[r]) - tab[r];
dif.insert(make_pair(cdi[r], r));
}
}
for(int i = 1; i <= n; ++i)
tim[i] = max(tim[i], 0);
tim[*cur.begin()] = II;
DoT(n);
//for(int i = 1; i <= n; ++i)
//cerr << tim[i] << " ";
//cerr << "\n";
}
int max_towers(int L, int R, int D)
{
++L; ++R;
int ans = Query(L, R, D);
if(ans == 0)
{
int p = FindXD(L, R, D);
int p2 = FindXD2(L, R, D);
//cerr << "Find: " << p << " " << QueryMI(p + 1, R) << "\n";
if(p == -1 || p2 == -1) return 1;
if(p <= p2) return 2;
return 1;
}
int l = FindL(1, 0, N - 1, L, R, D);
int r = FindR(1, 0, N - 1, L, R, D);
//cerr << "Que: " << l << " " << r << "\n";
if(l != L && ChkL(L, l - 1, D)) ++ans;
if(r != R && ChkR(r + 1, R, D)) ++ans;
return ans;
}
