#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)
{
for(int i = 1 ; i <= n ; i++)
tab[0][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 -inf;
int t = 31 - __builtin_clz(r - l + 1);
return max( tab[t][l] , tab[t][r - (1 << t) + 1] );
}
protected:
int tab[maxl][maxn];
};
int n;
int v[maxn];
int dp[maxn];
bool hasBuilt = false;
SparseTable st;
vector<int> valleys;
bool isValid(int i, int j, int D)
{
int peak = st.query( i + 1 , j - 1 );
if( v[i] <= peak - D && v[j] <= peak - D )
return true;
return false;
}
void build(int D)
{
for(int i = 1 ; i <= n ; i++)
{
while( !valleys.empty() )
{
int j = valleys.back();
if( isValid( j , i , D ) )
{
valleys.push_back( i );
break;
}
if( v[j] < v[i] )
break;
valleys.pop_back();
}
if( valleys.empty() )
valleys.push_back( i );
}
hasBuilt = true;
}
void init(int N, vector<int> H) {
n = N;
H.insert( H.begin() , 0 );
for(int i = 1 ; i <= n ; i++)
v[i] = H[i];
st.build( n , H );
}
int max_towers(int L, int R, int D)
{
if( !hasBuilt )
build( D );
L++; R++;
if( R - L + 1 <= 2 )
return 1;
int pL = lower_bound( valleys.begin() , valleys.end() , L ) - valleys.begin();
int pR = upper_bound( valleys.begin() , valleys.end() , R ) - valleys.begin();
if( pL == pR )
{
if( isValid( L , R , D ) )
return 2;
return 1;
}
int ans = pR - pL;
if( isValid( L , valleys[pL] , D ) )
ans++;
if( isValid( valleys[pR - 1] , R , D ) )
ans++;
return ans;
}
