#include "gap.h"
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long
const ll MAX = 1e18 ;
using namespace std ;
long long findGap(int T, int N)
{
if( T == 1 || N <= 7 )
{
vector<ll> a(N) ;
MinMax(0LL,MAX, &a[0] , &a[N-1] ) ;
for(int l = 1 , r = N-2 ; l <= r ; l++ , r-- )
MinMax(a[l-1]+1, a[r+1]-1, &a[l], &a[r] ) ;
ll resp = -1LL ;
for(int i = 0 ; i < N-1 ; i++ ) resp = max(resp, a[i+1]-a[i] ) ;
return resp ;
}
ll cur = -1 ,mn=-1 , mx=-1 , biggest=-1 ;
MinMax(0, MAX, &cur, &biggest ) ;
ll d = (biggest-cur+N)/N ;
while( true )
{
if( cur + d > biggest ) return d ;
MinMax(cur+1, cur+d, &mn, &mx ) ;
if( mx != -1 )
{
cur = mx ;
continue ;
}
ll l = cur+d+1, r = cur + (d<<1LL) ;
while( true )
{
MinMax(l, min(r, biggest), &mn, &mx ) ;
if( r >= biggest ) return ( mn == -1 ) ? d : (mn-cur) ;
if( mn != -1 )
{
d = mn - cur ;
cur = mn ;
break ;
}
ll auxL = r+1 ;
ll auxR = cur+((r-cur)<<1LL );
l = auxL ;
r = auxR ;
}
}
return d ;
}
