#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAX1=LLONG_MAX;
inline long long max1(long long a,long long b)
{
if(a>b)return a;
return b;
}
long long solve1(long long N)
{
long long l=0,r=MAX1,a,b,ans=0;
vector<long long> v;
for(long long i=0;i<N;i+=2)
{
MinMax(l,r,&a,&b);
v.push_back(a);
if(a!=b)v.push_back(b);
l=a+1;
r=b-1;
}
sort(v.begin(),v.end());
for(long long i=1;i<N;i++)
{
ans=max1(ans,v[i]-v[i-1]);
}
return ans;
}
long long solve2(long long N)
{
long long a,b,las,ans=0,x,y;
MinMax(0,MAX1,&a,&b);
long long k=(b-a+N-1)/(N-1);
las=a;
for(long long i=a;i<b;i+=k)
{
MinMax(i,i+k-1,&x,&y);
if(x==-1)continue;
ans=max1(ans,x-las);
las=y;
}
return ans;
}
long long findGap(int T, int N)
{
if(T==1)return solve1(N);
return solve2(N);
}
