#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 ;
long long findGap(int T, int N)
{
ll ans = 0 ;
if(T == 1){
ll lo = 0, hi = 1e18 ;
multiset<ll> s ;
int l = 0 , r = N - 1;
vector<ll> arr(N+1 , 0) ;
while(l<=r){
ll mn ,mx ;
MinMax(lo , hi , &mn , &mx) ;
arr[l] = mn ;
arr[r] = mx ;
l++ ;
r-- ;
lo = mn + 1 ;
hi = mx - 1;
}
for(int i =1 ;i < N ;i++)
ans = max(ans , arr[i] - arr[i-1]) ;
}
else{
ll mn , mx ;
MinMax(0 , 1e18 , &mn , &mx) ;
ll d = (mx - mn - 1) / (N - 1) ;
vector<ll> vec = {mn , mx } ;
assert(d) ;
ll cur = mn + 1 ;
while(cur < vec[1]){
MinMax(cur , cur + d - 1 , &mn , &mx) ;
cur+=d ;
if(mn == -1){
continue ;
}
vec.push_back(mn) ;
vec.push_back(mx) ;
}
sort(vec.begin() , vec.end()) ;
for(int i = 1 ; i < (int) vec.size() ;i ++){
ans = max(ans , vec[i] - vec[i-1] ) ;
}
}
return ans ;
}
