#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)
{
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);
if(N==2)return mx-mn;
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;
}
// queue<pair<ll,ll>> q;
// q.push({mn,mx});
// while(cnt>0&&!q.empty())
// {
// ll l=q.front().fi,r=q.front().se;
// q.pop();
// if(l+1==r||l==r)
// {
// ans=max(ans,r-l);
// continue;
// }
// ll mid=(l+r)>>1;
// ll mn1,mx1;
// MinMax(l,mid,&mn1,&mx1);
// ll mn2,mx2;
// MinMax(mid+1,r,&mn2,&mx2);
// if(mn1==-1&&mx1==-1&&mn2==-1&&mx2==-1)ans=max(ans,r-l);
// if(mn1!=-1)
// {
// cnt--;
// if(mn1!=mx2)cnt--;
// }
// if(mn2!=-1)
// {
// cnt--;
// if(mn2!=mx2)cnt--;
// }
// if(mx1!=-1&&mn2!=-1)ans=max(ans,mn2-mx1);
// if(mn1!=-1)ans=max(ans,mn1-l);
// else if(mn2!=-1)ans=max(ans,mn2-l);
// if(mx2!=-1)ans=max(ans,r-mx2);
// else if(mx1!=-1)ans=max(ans,r-mx1);
// if(mn1!=mx1&&mx1-mn1>ans)q.push({mn1,mx1});
// if(mn2!=mx2&&mx2-mn2>ans)q.push({mn2,mx2});
// }
// return (ll)ans;
}
