#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
long long findGap(int T, int N)
{
ll ret = 0;
if(T==1){
vector<ll> v1, v2;
ll mn= 0, mx = 1e18;
while(mn<=mx){
ll MN=-1,MX=-1;
MinMax(mn,mx,&MN,&MX);
if(MN<0)break;
v1.push_back(MN); v2.push_back(MX);
if(sz(v1)+sz(v2)>=N)break;
mn=MN+1,mx=MX-1;
}
reverse(all(v2));
for(auto i : v2)v1.push_back(i);
for(int i = 1 ; i < sz(v1) ; i++)ret=max(ret,v1[i]-v1[i-1]);
}
else{
ll mn=0, mx=1e18;
ll MN=-1,MX=-1;
MinMax(mn,mx,&MN,&MX);
if(N==2)return MX-MN;
ll t = (MX-MN+N-2)/(N-1);
ret=t;
vector<ll> v;
mn=MN,mx=MX;
v.push_back(MN);
for(ll i = mn+1 ; i < mx ; i+=t){
// cout<<i<<endl;
MinMax(i,i+t-1,&MN,&MX);
if(MN>=0){
ret=max(ret, MN-v.back());
v.push_back(MX);
}
}
}
return ret;
}
