#include<bits/stdc++.h>
#include "gap.h"
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define I inline void
using ll = long long ;
using ld = long double ;
using namespace std ;
const int mod = 1e9 + 7 ;
// how interesting!
int n;
vector<ll> v ;
ll zero = -1 ;
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 = &zero , *mx = &zero;
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 ;
mn = mx = &zero ;
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;
}
