#include<iostream>
#include "gap.h"
using namespace std;
#define ll long long
int c;
ll b, x, y, pre, lo=0, ans, hi=1000000000000000000LL;
/*void MinMax(ll lo, ll hi, ll *x, ll *y){
c++;
if (lo>728704890713443211 || hi<29659227736649406){
*x=*y=-1;
return;
}
if (lo<=29659227736649406) *x=29659227736649406;
else *x=728704890713443211;
if (hi>=728704890713443211) *y=728704890713443211;
else *y=29659227736649406;
}*/
ll findGap(int t, int n){
MinMax(lo, hi, &lo, &hi);
if (t==1){
if (n<3) return hi-lo;
for (int l=0; l<(n-1)/2; ++l){
MinMax(lo+1, max(lo+1, hi-1), &x, &y);
if (x==-1) break;
ans=max(ans, max(x-lo, hi-y));
if (x==y) break;
if (l==(n-1)/2-1) ans=max(ans, y-x);
lo=x; hi=y;
}
return ans;
}
b=(hi-lo+n-2)/n;
pre=lo; ans=0;
//cout << lo << ' ' << hi << ' ' << b << endl;
for (ll l=lo+1; l<hi; l+=b){
//cout << l << ' ' << endl;
MinMax(l, min(hi, l+b-1), &x, &y);
if (x==-1) continue;
ans=max(ans, x-pre); pre=y;
}
ans=max(ans, hi-pre);
return ans;
}
/*int main(){
cout << findGap(1, 2) << ' '; cout << c;
return 0;
}*/
