#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
long long findGap(int T, int n)
{
if(T == 1) {
vector<ll> a(n);
ll l = 0, r = 1e18;
int i = 0, j = n - 1;
while(i <= j) {
ll mn, mx;
MinMax(l, r, &mn, &mx);
a[i] = mn;
a[j] = mx;
l = mn + 1;
r = mx - 1;
++i;
--j;
}
ll ans = 0;
for(int i=0;i<n-1;++i)
ans = max(ans, a[i + 1] - a[i]);
return ans;
} else {
vector<ll> a;
ll mn, mx;
MinMax(0, 1e18, &mn, &mx);
if(n == 2)
return mx - mn;
ll l = mn, r = mx;
++l; --r;
ll gaps = (r - l + (n - 2) - 1) / (n - 2);
a.push_back(mn);
a.push_back(mx);
ll st = l, en, st2;
while(st < r && a.size() < n) {
st2 = st;
en = min(r, st2 + gaps - 1);
while(st2 <= en && mn != st2 && a.size() < n) {
MinMax(st2, en, &mn, &mx);
if(mn == -1)
break;
a.push_back(mn);
if(mn != mx) {
a.push_back(mx);
}
st2 = mn + 1;
en = mx - 1;
}
st += gaps;
}
ll ans = 0;
sort(a.begin(), a.end());
for(int i=1;i<n;++i)
ans = max(a[i] - a[i - 1], ans);
return ans;
}
}
