#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(mn == -1) return 0; // no numbers at all
a.push_back(mn);
a.push_back(mx);
ll l = mn + 1;
ll r = mx - 1;
// compute a reasonable "gap size" to split the interval
ll step = (mx - mn + N - 1) / N; // ceil((mx - mn)/N)
// iterate over chunks
ll start = l;
while(a.size() < N && start <= r) {
ll end = min(r, start + step - 1);
ll mn2, mx2;
MinMax(start, end, &mn2, &mx2);
if(mn2 != -1) {
a.push_back(mn2);
if(mx2 != mn2) a.push_back(mx2);
}
start = end + 1;
}
sort(a.begin(), a.end());
// trim to N elements (if we added extra)
while(a.size() > N) a.pop_back();
ll ans = 0;
for(int i=0;i<N-1;++i)
ans = max(ans, a[i + 1] - a[i]);
return ans;
}
}
