#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;
#include "towers.h"
int n , a[ N ] ;
pair < int , int > node[ 4 * N ] ;
void build( int v , int vl , int vr ){
if( vl == vr ){
node[ v ] = { a[ vl - 1 ] , vl - 1 } ;
return ;
}
int vm= ( vl + vr ) / 2 ;
build( v + v , vl , vm ) ;
build( v + v + 1 , vm + 1 , vr ) ;
node[ v ] = max( node[ v + v ] , node[ v + v + 1 ] ) ;
return ;
}
pair < int , int > get( int v , int vl , int vr , int l , int r ){
if( l > r ) return { 0 , 0 } ;
if( vl == l && vr == r ) return node[ v ] ;
int vm = ( vl + vr ) / 2 ;
pair < int , int > a , b ;
a = get( v + v , vl , vm, l , min( r , vm ) ) ;
b = get( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
return max( a , b ) ;
}
void init(int N, std::vector<int> H){
n = N ; FOR( i , N ) a[ i ] = H[ i ] ;
// if this works make it into segment tree ?
build( 1 , 1 , n ) ;
return ;
}
map < pair < int , pair < int , int > > , int > dp ;
int get( int l , int r , int mx , int d ){
pair < int , pair < int , int > > axla ;
axla.f = l ; axla.s.f = r ; axla.s.s = mx ;
if( dp.find( axla ) != dp.end() ) return dp[ axla ] ;
if( l > r ) return 0 ;
if( l == r && a[ l ] <= mx ) return 1 ;
if( l == r ) return 0 ;
pair < int , int > p ;
p = get( 1 , 1 , n , l + 1 , r + 1 ) ;
int cur_max = p.f ;
int cur_pos = p.s ;
int pas = 0 ;
// now case work
if( cur_max <= mx ) pas = 1 ;
int A , B ;
// first both sides
A = get( l , cur_pos - 1 , cur_max - d , d ) ;
B = get( cur_pos + 1 , r , cur_max - d , d ) ;
pas = max( pas , A + B ) ;
// only left side
A = get( l , cur_pos - 1 , mx , d ) ;
pas = max( pas , A ) ;
// only right
B = get( cur_pos + 1 , r , mx , d ) ;
pas = max( pas , B ) ;
// Done? Hopefully
dp[ axla ] = pas ;
return pas ;
}
int max_towers(int L, int R, int D){
pair < int , int > p ;
p = get( 1 , 1 , n , L + 1 , R + 1 ) ;
int mx = p.f ;
int pos = p.s ;
return max( 1 , ( get( L , pos - 1 , mx , D ) + get( pos + 1 , R , mx - D , D ) ) ) ;
}
// int main() {
// int N, Q;
// assert(2 == scanf("%d %d", &N, &Q));
// std::vector<int> H(N);
// for (int i = 0; i < N; ++i) {
// assert(1 == scanf("%d", &H[i]));
// }
// init(N, H);
// for (int i = 0; i < Q; ++i) {
// int L, R, D;
// assert(3 == scanf("%d %d %d", &L, &R, &D));
// printf("%d\n", max_towers(L, R, D));
// }
// return 0;
// }
