#include "gap.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int findGap(int32_t t, int32_t n){
if(t==1){
int arr[n];
int l=0;
int r=1e18;
for(int x=0;x<(n+1)/2;x++){
MinMax(l,r,&arr[x],&arr[n-1-x]);
l=arr[x]+1;
r=arr[n-1-x]-1;
}
int best=0;
for(int x=1;x<n;x++){
best=max(best,arr[x]-arr[x-1]);
}
return best;
}
pii hold;
MinMax(0,1e18,&hold.first,&hold.second);
int len=(hold.second-hold.first-1)/n;
int cur=hold.first+1;
vector<pii>v;
v.push_back({hold.first,hold.first});
pii hold2;
for(int x=0;x<n-3;x++){
MinMax(cur,cur+len-1,&hold2.first,&hold2.second);
cur+=len;
v.push_back(hold2);
}
if(cur<=hold.second-1){
MinMax(cur,hold.second-1,&hold2.first,&hold2.second);
v.push_back(hold2);
}
v.push_back({hold.second,hold.second});
int best=0;
int lst=1e18;
for(int x=0;x<(int)v.size();x++){
if(v[x].first==-1) continue;
//best=max(best,v[x].second-v[x].first);
best=max(best,v[x].first-lst);
lst=v[x].second;
}
return best;
}
