#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxl = 20;
const int maxn = 100010;
const int inf = 1000000010;
class SparseTable
{
public:
void build(int n, vector<int> v, bool mn = false)
{
isMin = mn;
for(int i = 1 ; i <= n ; i++)
tab[0][i] = (mn ? -v[i] : v[i]);
for(int k = 1 ; k < maxl ; k++)
for(int i = 1 ; i + (1 << k) - 1 <= n ; i++)
tab[k][i] = max( tab[k - 1][i] , tab[k - 1][i + (1 << (k - 1))] );
}
int query(int l, int r)
{
if( l > r )
return (isMin ? inf : -inf);
int t = 31 - __builtin_clz(r - l + 1);
int ans = max( tab[t][l] , tab[t][r - (1 << t) + 1] );
return (isMin ? -ans : ans);
}
protected:
bool isMin;
int tab[maxl][maxn];
};
int n;
int v[maxn];
SparseTable stV;
vector<int> ans;
vector<int> valleys;
void findValleys()
{
v[0] = v[n + 1] = inf;
for(int i = 1 ; i <= n ; i++)
if( v[i - 1] > v[i] && v[i] < v[i + 1] ) valleys.push_back( i );
for(int i = 0 ; i < (int)valleys.size() - 1 ; i++)
{
int peak = stV.query( valleys[i] + 1 , valleys[i + 1] - 1 );
int diff = min( peak - v[ valleys[i] ] , peak - v[ valleys[i + 1] ] );
ans.push_back( diff );
}
}
void init(int N, vector<int> H) {
n = N;
H.insert( H.begin() , 0 );
stV.build( n , H );
for(int i = 1 ; i <= n ; i++)
v[i] = H[i];
findValleys();
}
int max_towers(int L, int R, int D)
{
int t = upper_bound( ans.begin() , ans.end() , D ) - ans.begin();
return t + 1;
}
