#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long findGap(signed t,signed n)
{
if (t==2)
{
ll mn1,mx1,lim1=0,lim2=1e18,mn,mx;
MinMax(lim1,lim2,&mn1,&mx1);
ll s=0,e=1e18;
while (s+1<e)
{
ll mid = (s+e)/2, l = mn1;
bool b=0;
while (l+mid<mx1)
{
MinMax(l+1,l+mid,&mn,&mx);
if (mn==-1)
{
b=1;
break;
}
l=mx;
}
if (b)
s=mid;
else
e=mid;
}
return s+1;
}
else
{
long long a[n],i=0,j=n-1,lim1=0,lim2=1e18;
long long mn,mx;
while (i<=j)
{
MinMax(lim1,lim2,&mn,&mx);
a[i++]=mn;
a[j--]=mx;
lim1=mn+1;
lim2=mx-1;
}
long long ans=0;
for (int i=0;i<n-1;i++)
ans=max(ans,a[i+1]-a[i]);
return ans;
}
}
