#include "gap.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
long long findGap(int T, int N)
{
if(T==1||N<=10)
{
ll ans=0;
ll mn,mx;
MinMax((ll)0,(ll)1e18,&mn,&mx);
if(N==2)return mx-mn;
for(int i=0;i<(N-1)/2;i++)
{
ll mn1,mx1;
MinMax(mn+1,mx-1,&mn1,&mx1);
ans=max(ans,mn1-mn);
ans=max(ans,mx-mx1);
mn=mn1;
mx=mx1;
}
ans=max(ans,mx-mn);
return ans;
}
else
{
ll ans=0;
ll mn,mx;
MinMax((ll)0,(ll)1e18,&mn,&mx);
ans=(mx-mn-1)/(N-1)+1;
ll a=mn;
while(a<mx)
{
ll mn1,mx1;
ll temp;
MinMax(a+1,a+ans+1,&mn1,&mx1);
if(mn1==-1&&mx1==-1)
{
temp=a+ans+1;
while(true)
{
MinMax(temp+1,a+(temp+1-a)*2,&mn1,&mx1);
if(mn1==-1&&mx1==-1)
{
temp=a+(temp+1-a)*2;
continue;
}
ans=mn1-a;
a=mx1;
break;
}
}
else
{
if(mn1==a+ans+1&&mx1==a+ans+1)ans+=1;
a=mx1;
}
}
return ans;
}
}
