#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;
while(1)
{
MinMax(left, right, &mn, &mx);
if(mn == -1)
{
curgap += gap;
left = right + 1;
right = left + gap -1;
}
else
{
curgap += mn - left + 1;
gap = max(gap, curgap);
curgap = 0;
left = mx + 1;
right = mx + gap;
}
if(mn == rightmost) break;
}
return gap;
}
}
