#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll findGap(int T, int N) {
ll ans = 0;
ll mn, mx;
MinMax(0, 1'000'000'000'000'000'000LL, &mn, &mx);
if (T == 1) {
for (int i = 1; i < (N + 1) / 2; ++i) {
ll mn2, mx2;
MinMax(mn + 1, mx - 1, &mn2, &mx2);
ans = max({ans, mn2 - mn, mx - mx2});
mn = mn2;
mx = mx2;
}
ans = max(ans, mx - mn);
} else if (T == 2) {
const ll min_gap = 1 + (mx - mn - 1) / (N - 1);
ll last = mn;
for (ll l = mn + 1; l < mx; l += min_gap) {
ll r = min(mx - 1, l + min_gap);
ll mn2, mx2;
MinMax(l, r, &mn2, &mx2);
if (mn2 != -1) {
ans = max(ans, mn2 - last);
last = mx2;
}
}
ans = max(ans, mx - last);
}
return ans;
}
