#include <bits/stdc++.h>
#include <stdlib.h>
#include "gap.h"
#define I inline void
using ll = long long ;
using ld = long double ;
using namespace std ;
const int mod = 1e9 + 7 ;
struct node{
ll pref = 0 , suff = 0 , summ = 0 , mxx = 0 ;
I maint(){
mxx = max(max(mxx , pref) , max(suff , summ)) ;
}
node(){
}
node(ll x){
pref = suff = summ = x ;
maint() ;
}
I merge(node &rhs){
ll npref = 0 , nsuff = 0 , nsumm = 0 ;
if(summ){
npref = summ + rhs.pref ;
}
else npref = pref ;
if(summ && rhs.summ){
nsumm = summ + rhs.summ ;
}
if(rhs.summ){
nsuff = rhs.summ + suff ;
}
else nsuff = rhs.suff ;
mxx = max(mxx , suff + rhs.pref) ;
pref = npref ;
summ = nsumm ;
suff = nsuff ;
mxx = max(mxx , rhs.mxx) ;
maint() ;
}
} ;
node query(ll L , ll R){
ll mn , mx ;
if(L == R){
MinMax(L , R , &mn , &mx) ;
return node( mn == -1) ;
}
ll mid = (L + R) >> 1ll ;
MinMax(L , R , &mn , &mx) ;
if( mn == -1){
return node(R - L + 1) ;
}
if(L == R)
return node(0) ;
node lhs = query(L , mid) ;
node rhs = query(mid+1 , R) ;
lhs.merge(rhs) ;
return lhs ;
}
long long findGap(int T, int N)
{
ll st = 0 , en = 1e18 ;
ll mn , mx ;
ll lo = 0, hi = 1e18 ;
while(lo<=hi){
ll mid = (lo + hi ) >> 1ll ;
MinMax(0 , mid , &mn , &mx) ;
if( mx != -1){
st = mid ;
hi = mid -1 ;
}
else lo = mid + 1;
}
lo = 0 , hi = 1e18 ;
while(lo<=hi){
ll mid = (lo + hi ) >> 1ll ;
MinMax(mid , 1e18 , &mn , &mx ) ;
if( mx != -1){
en = mid ;
lo = mid +1 ;
}
else
hi = mid - 1;
}
node answer = query(st , en) ;
return answer.mxx + 1;
return 0;
}
