#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
long long findGap(int T, int N)
{
if(T == 1)
{
long long mn, mx;
long long left = 0, right = 1000000000000000000;
long long gap = 1;
MinMax(left, right, &mn, &mx);
left = mn + 1;
right = mx - 1;
int i = 1;
while(left <= right)
{
if(i == (N+1)/2)
{
gap = max(gap, mx - mn);
break;
}
long long newmn, newmx;
MinMax(left, right, &newmn, &newmx);
gap = max(max(gap, newmn - mn), mx - newmx);
left = newmn + 1;
right = newmx - 1;
mn = newmn;
mx = newmx;
i++;
}
return gap;
}
else
{
long long mn, mx;
long long left = 0, right = 1000000000000000000;
MinMax(left, right, &mn, &mx);
long long rightmost = mx;
long long gap = (mx - mn + N-2)/(N-1);
left = mn + 1;
right = mn + gap;
long long curgap = 0;
int i = 0;
while(1)
{
// if(i < 100)
// {
// cout << "left = " << left << ", right = " << right << "\n";
// }
MinMax(left, right, &mn, &mx);
if(mn == -1)
{
curgap += gap;
}
else
{
curgap += mn - left + 1;
gap = max(gap, curgap);
curgap = right - mx;
}
left = right + 1;
right = left + gap -1;
if(mx == rightmost) break;
// if(i < 100)
// {
// cout << "mn = " << mn << ", mx = " << mx << ", curgap = " << curgap << ", gap = " << gap << "\n\n";
// i++;
// }
}
return gap;
}
}
