#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll findGap(int T, int N) {
if (T == 1) {
vector<ll> a;
ll s = 0, t = 1e18+1, mn = 0, mx = 0;
for (int i = 0; i < (N+1)/2; i++) {
MinMax(s, t, &mn, &mx);
if (mn != -1) a.push_back(mn);
if (mx != -1 && mx != mn) a.push_back(mx);
s = mn+1, t = mx-1;
}
sort(a.begin(), a.end());
ll ans = -1;
for (int i = 0; i < N-1; i++) ans = max(ans, a[i+1] - a[i]);
return ans;
} else {
ll s = 0, t = 1e18+1, mn = 0, mx = 0;
MinMax(s, t, &mn, &mx);
ll density = (mx - mn + N) / N;
ll ans = density, curs = mn, tmx = mx;
// cout << "density: " << density << "\n";
while (curs < tmx) {
s = curs+1, t = curs;
mn = -1;
while (mn == -1) {
t += density;
MinMax(s, t, &mn, &mx);
}
ans = max(ans, mn - curs);
density = ans;
curs = mx;
}
return ans;
}
return 0;
}
