#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"
// first type of segment tree
struct stu{
int mn , mx , val , val1 , pos ;
};
stu node[ 4 * N ] , xx ;
int a[ N ] , n ;
stu combine( stu a , stu b ){
stu c ; c.mx = max( a.mx , b.mx ) ;
c.mn = min( a.mn , b.mn ) ;
c.val = max( { a.val , b.val , b.mx - a.mn } ) ;
c.val1 = max( { a.val1 , b.val1 , a.mx - b.mn } ) ;
if( a.mn < b.mn ) c.pos = a.pos ;
else c.pos = b.pos ;
return c ;
}
void build( int v , int vl , int vr ){
if( vl == vr ){
node[ v ] = { a[ vl ] , a[ vl ] , 0 , 0 , vl } ;
return ;
}
int vm = ( vl + vr ) / 2 ;
build( v + v , vl , vm ) ;
build( v + v + 1 , vm + 1 , vr ) ;
node[ v ] = combine( node[ v + v ] , node[ v + v + 1 ] ) ;
}
stu get_df( int v , int vl , int vr , int l , int r ){
if( l > r ) return xx ;
if( vl == l && vr == r ) return node[ v ] ;
int vm = ( vl + vr ) / 2 ;
stu a , b ;
a = get_df( v + v , vl , vm , l , min( r , vm ) ) ;
b = get_df( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
return combine( a , b ) ;
}
int get_clos( int v , int vl , int vr , int l , int r , int val , int nd ){
if( l > r ) return -1 ;
if( node[ v ].mx < val ) return -1 ;
if( vl == vr ) return vl ;
int vm = ( vl + vr ) / 2 ;
// nd == -1 --> marcxnidan
// nd == 1 --> marjvnidan
if( nd == -1 ){
int x = -1 ;
if( node[ v + v + 1 ].mx >= val ){
x = get_clos( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r , val , nd ) ;
}
if( x == -1 )
x = get_clos( v + v , vl , vm , l , min( r , vm ) , val , nd ) ;
return x ;
}
else{
int x = -1 ;
if( node[ v + v ].mx >= val ){
x = get_clos( v + v , vl , vm , l , min( r , vm ) , val , nd ) ;
}
if( x == -1 )
x = get_clos( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r , val , nd ) ;
return x ;
}
}
// now you need a new persistent_seg_tree with decreasing Diff
// anu ginda jami da yvelaze marcx_yvelaze_marjv
int clos_l[ N ] , clos_r[ N ] ;
map < int , int > lst ;
int cc = 2 ;
pair < int , int > sn[ 20 * N ] ;
int jm[ 20 * N ] ;
void build_ot( int v , int vl , int vr ){
if( vl == vr ){
jm[ v ] = 0 ; return ;
}
int vm = ( vl + vr ) / 2 ;
sn[ v ].f = cc ; cc ++ ;
build_ot( sn[ v ].f , vl , vm ) ;
sn[ v ].s = cc ; cc ++ ;
build_ot( sn[ v ].s , vm + 1 , vr ) ;
jm[ v ] = 0 ;
return ;
}
void update_ot( int v , int pp , int vl , int vr , int pos ){
if( vl == vr ){
jm[ v ] = 1 ;
return ;
}
int vm = ( vl + vr ) / 2 ;
if( vm >= pos ){
sn[ v ].f = cc ; cc ++ ;
sn[ v ].s = sn[ pp ].s ;
update_ot( sn[ v ].f , sn[ pp ].f , vl , vm , pos ) ;
}
else{
sn[ v ].s = cc ; cc ++ ;
sn[ v ].f = sn[ pp ].f ;
update_ot( sn[ v ].s , sn[ pp ].s , vm + 1 , vr , pos ) ;
}
jm[ v ] = jm[ sn[ v ].f ] + jm[ sn[ v ].s ] ;
}
int sum( int v , int vl , int vr , int l , int r ){
if( l > r ) return 0 ;
if( vl == l && vr == r ) return jm[ v ] ;
int vm = ( vl + vr ) / 2 ;
int a , b ;
a = sum( sn[ v ].f , vl , vm , l , min( r , vm ) ) ;
b = sum( sn[ v ].s , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
return ( a + b ) ;
}
int get_ert( int v , int vl , int vr , int l , int r , int tp ){
if( l > r ) return -1 ;
if( jm[ v ] == 0 ) return -1 ;
if( vl == vr ) return vl ;
int vm = ( vl + vr ) / 2 ;
// -1 --> marcxena
// 1 --> marjvena
if( tp == -1 ){
int x = -1 ;
if( jm[ sn[ v ].f ] != 0 ){
x = get_ert( sn[ v ].f , vl , vm , l , min( r , vm ) , tp ) ;
}
if( x == -1 ) x = get_ert( sn[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r , tp ) ;
return x ;
}
else{
int x = -1 ;
if( jm[ sn[ v ].s ] != 0 ){
x = get_ert( sn[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r , tp ) ;
}
if( x == -1 ) x = get_ert( sn[ v ].f , vl , vm , l , min( r , vm ) , tp ) ;
return x ;
}
}
set < pair < int , int > > se ;
stack < int > st ; set < int > sis ;
void init(int N, std::vector<int> H){
n = N ; FOR( i , N ) a[ i + 1 ] = H[ i ] ;
// if this works make it into segment tree ?
xx.mn = 1e9 + 1 ; xx.mx = -1e9 - 1 ; xx.val = 0 ; xx.val1 = 0 ; xx.pos = -1 ;
build( 1 , 1 , n ) ;
build_ot( 1 , 1 , n ) ;
// left to right
for( int j = 1 ; j <= n ; j ++ ){
while( true ){
if( st.size() == 0 ) break ;
if( a[ st.top() ] > a[ j ] ){
st.pop() ;
} else break ;
}
if( st.size() == 0 ){
clos_l[ j ] = 0 ;
} else clos_l[ j ] = st.top() ;
st.push( j ) ;
}
// right to left
while( st.size() > 0 ) st.pop() ;
for( int j = n ; j >= 1 ; j -- ){
while( true ){
if( st.size() == 0 ) break ;
if( a[ st.top() ] > a[ j ] ){
st.pop() ;
} else break ;
}
if( st.size() == 0 ){
clos_r[ j ] = n + 1 ;
} else clos_r[ j ] = st.top() ;
st.push( j ) ;
}
vector < pair < int , int > > v ;
for( int j = 1 ; j <= n ; j ++ ){
if( clos_l[ j ] == j - 1 || clos_r[ j ] == j + 1 ) continue ;
stu bb = get_df( 1 , 1 , n , clos_l[ j ] + 1 , j ) ;
stu aa = get_df( 1 , 1 , n , j , clos_r[ j ] - 1 ) ;
bb.mx = min( bb.mx , aa.mx ) ;
int af = bb.mx - a[ j ] ;
v.pb( { af , j } ) ;
//cout << af << " " << j << endl ;
}
sort( v.begin() , v.end() ) ;
// now slowly create persistent seg tree
int bef = 1 ;
for( int j = v.size() - 1 ; j >= 0 ; j -- ){
pair < int , int > p ;
p = v[ j ] ;
int cur = cc ; cc ++ ;
lst[ p.f ] = cur ;
update_ot( cur , bef , 1 , n , p.s ) ;
bef = cur ;
sis.insert( p.f ) ;
}
for( auto x : sis ){
se.insert( { x , lst[ x ] } ) ;
}
}
int check( int l , int r , int pos , int tp , int d ){
// -1 --> marcxnidan
// 1 --> marjvnidan
if( tp == -1 ){
int xix = get_clos( 1 , 1 , n , l , pos , a[ pos ] + 1 , -1 ) ;
if( xix == -1 ) return 0 ;
stu ch = get_df( 1 , 1 , n , l , xix ) ;
if( ch.val < d ) return 0 ;
return 1 ;
}
if( tp == 1 ){
int xix = get_clos( 1 , 1 , n , pos , r , a[ pos ] + 1 , 1 ) ;
if( xix == -1 ) return 0 ;
stu ch = get_df( 1 , 1 , n , xix , r ) ;
if( ch.val1 < d ) return 0 ;
return 1 ;
}
}
int max_towers(int L, int R, int D){
L ++ ; R ++ ;
pair < int , int > p ; p.s = 1 ;
if( se.size() != 0 )
if( (*(--se.end() )).f >= D )
p = *(se.lower_bound( { D , 0 } ) ) ;
int root = p.s ;
// now calculate the answerr
int ans = sum( root , 1 , n , L , R ) ;
// if( L == 1 && R == n ) return ans ;
if( ans == 0 ){
stu cur ; cur = get_df( 1 , 1 , n , L , R ) ;
int pos = cur.pos ;
if( check( L , R , pos , -1 , D ) == 1 || check( L , R , pos , 1 , D ) == 1 ) return 2 ;
return 1 ;
}
// else we have left_right
int lf = get_ert( root , 1 , n , L , R , -1 ) ;
int rg = get_ert( root , 1 , n , L , R , 1 ) ;
// cout << lf << " " << rg << endl ;
if( lf != -1 )
ans = ans + check( L , R , lf , -1 , D ) ;
if( rg != -1 )
ans = ans + check( L , R , rg , 1 , D ) ;
return ans ;
}
// 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;
// }
