#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long INF = 1e18;
long long findGap(int T, int N){
if(T==1){
ll mn = 0, mx = INF;
ll l=0,r=N-1;
vector<ll>a(N);
while(l <= r){
MinMax(mn,mx,&mn,&mx);
a[l++]=mn;
a[r++]=mx;
mn+=1;mx-=1;
}
ll diff = 0;
for(int i=1;i<N;i++){
diff=max(diff,a[i]-a[i-1]);
}
return diff;
}
ll mn = 0, mx = INF;
MinMax(mn,mx,&mn,&mx);
ll min_diff = (mx - mn) / (N - 1) + 1;
ll ans = 0, prev = -INF;
for(ll i = mn; i <= mx; i += min_diff){
ll l, r;
MinMax(i,i+min_diff-1,&l,&r);
if( l == -1 )continue;
if( prev == -INF ) prev = l;
ans = max(ans, l - prev);
ans = max(ans, r - l);
prev = r;
}
return ans;
}
