#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
using vll = vector<long long>;
ll solveST1(ll n)
{
vll arr;
vll barr;
ll mn,mx;
ll p1=1;
ll p2=n;
ll lb=0;
ll ub=1000000000000000000ll;
while(p1<p2)
{
MinMax(lb,ub,&mn,&mx);
arr.push_back(mn);
barr.push_back(mx);
lb=mn+1;
ub=mx-1;
p1+=1;
p2-=1;
}
if(p1==p2)
{
MinMax(lb,ub,&mn,&mx);
arr.push_back(mn);
}
reverse(barr.begin(),barr.end());
for(auto num:barr)
arr.push_back(num);
ll ans=1;
for(int i=1;i<n;i++)
ans=max(ans,arr[i]-arr[i-1]);
return ans;
}
ll solveST2(int n)
{
ll ans=1;
ll lb,ub;
MinMax(1,1000000000000000000ll,&lb,&ub);
ll l,r,mid;
vll arr;
ll m=1;
l=2;r=(1000000000000000001ll+n)/(n-1);
while(l<=r)
{
mid=l+(r-l)/2;
ll val=lb+mid*(n-2);
if(val>=ub||ub-val<mid)
{
r=mid-1;
continue;
}
if(ub-val==mid)
{
m=mid;
l=r+1;
}
else
{
m=mid+1;
l=mid+1;
}
}
ans=m;
ll prev=lb;
ll idx=lb-1;;
ll mn,mx;
while(1)
{
MinMax(idx+1,idx+1+m,&mn,&mx);
idx=idx+1+m;
if(mn==-1)
continue;
ans=max(ans,mn-prev);
prev=mx;
if(mx==ub)
break;
}
return ans;
}
long long findGap(int T, int N)
{
if(T==1)
return solveST1(N);
else
return solveST2(N);
}
