#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll INF=1e18;
#include "gap.h"
ll findGap(int T, int n){
if(T==1){
vector<ll>v(n);
ll l=0, r=INF, idl=0, idr=n-1;
while(idl<=idr){
ll a=-1, b=-1;
MinMax(l,r,&a,&b);
l=a; r=b;
v[idl]=l; v[idr]=r;
l++; r--;
idl++; idr--;
}
ll resp=0;
for(int i=1;i<n;i++) resp=max(resp,v[i]-v[i-1]);
return resp;
}
ll mn, mx, a1, an;
MinMax(0, INF, &mn, &mx);
if(n == 2) return mx-mn;
a1 = mn; an = mx;
ll A = mx-mn;
ll B = A/(n-1);
//[0, B] [B+1, 2B+1] ..
vector<pair<ll, ll>> intervals;
for(ll i = a1; i <= an; i+=B+1){
ll l = i, r = i+B;
MinMax(l, r, &mn, &mx);
if(mn == -1) continue;
intervals.emplace_back(mn, mx);
}
ll resp = 0;
for(int i = 1; i < intervals.size(); i++){
resp = max(intervals[i].first-intervals[i-1].second, resp);
}
return resp;
}
