#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];
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;
void DoT(int n)
{
drz2[N] = II;
for(int i = 1; i <= n; ++i)
{
drz[i + N] = tim[i]; drz2[i + N] = tim[i];
mrg[i + N] = {tim[i]};
}
for(int i = n + 1; i < N; ++i) drz2[i + N] = II;
for(int i = N - 1; i >= 1; --i)
{
drz[i] = max(drz[2 * i], drz[2 * i + 1]);
drz2[i] = min(drz2[2 * i], drz2[2 * i + 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));
}
}
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)
{
int ans = Query(L + 1, R + 1, D);
return ans;
}
