#include "gap.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
long long findGap(int T, int N){
if (T==1){
long long arr[N];
int s=0,e=N-1;
long long a=0,b=1000000000000000000,sm,lm;
while (e-s>0){
MinMax(a,b,&sm,&lm);
arr[s]=sm,arr[e]=lm;
a=sm+1,b=lm-1;
s++,e--;
}
if (e==s){
MinMax(a,b,&sm,&lm);
arr[e]=sm;
}
long long maximal=0;
for (int x=1;x<N;x++){
maximal=max(maximal,arr[x]-arr[x-1]);
}
return maximal;
}
else{
vector<long long> v;
long long small,big;
MinMax(0,1000000000000000000,&small,&big);
long long gap=(big-small)/((long long) N-1);
long long si=small,se=small+(gap++);
long long mn,mx;
while (si<=big){
MinMax(si,se,&mn,&mx);
if(mn!=-1){
v.push_back(mn);
if (mx!=mn) v.push_back(mx);
}
si+=gap,se+=gap;
}
long long maximal=0;
for (int it=1;it<v.size();it++){
maximal=max(maximal,v[it]-v[it-1]);
}
return maximal;
}
}
