#include "gap.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long findGap(int T, int N)
{
if(T == 1)
{
vector<long long> a;
a.reserve(N);
long long s = 0, e = 1e18;
while(int(a.size()) < N)
{
MinMax(s, e, &s, &e);
assert(s != -1);
a.push_back(s); a.push_back(e);
++s;
--e;
}
sort(a.begin(), a.end());
long long ans = 0;
for(int i = 0; i < int(a.size()) - 1; ++i)
ans = max(ans, a[i + 1] - a[i]);
return ans;
}
long long a1 = 0, aN = 0;
MinMax(0, (long long)1e18, &a1, &aN);
long long d = (aN - a1 + N - 2) / (N - 1), ans = d;
for(long long i=a1, p=a1; i<=aN; i+=d+1)
{
long long s = 0, e = 0;
MinMax(i, min(i + d, aN), &s, &e);
if(~s)
ans = max(ans, s - p), p = e;
}
return ans;
}
