#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)
{
int cnt=N;
ll A=1e18;
ll ans=0;
ll mn,mx;
MinMax((ll)0,A,&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;
//ans=(mx-mn-1)/(N-1)+1;
// int 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;
// }
// cout<<a<<" "<<ans<<endl;
// }
// 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;
}
