#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long findGap(int t, int n) {
if (t == 1) {
ll mn = -1, mx = 1e18 + 1, l = 0, r = 1e18, ans = 0;
vector<ll> a;
for (int i = 1; i <= (n + 1) / 2; i++) {
MinMax(l, r, &mn, &mx);
if (mn < 0 or mx < 0) break;
l = mn + 1;
r = mx - 1;
a.push_back(mn);
a.push_back(mx);
}
sort(a.begin(), a.end());
int len = a.size();
for (int i = 1; i < len; i++) {
ans = max(ans, a[i] - a[i - 1]);
}
return ans;
}
else {
ll first, last, l = 0, ans = 0;
MinMax(l, 1e18, &first, &last);
ll dif = (last - first + n - 2) / (n - 1);
ans = dif; l = first;
for (ll i = l + 1; i < last; i += dif + 1) {
ll mn, mx;
MinMax(i, min(i + dif, last - 1), &mn, &mx);
if (mn == -1) continue;
ans = max(ans, mn - l);
l = mx;
}
ans = max(ans, last - l);
return ans;
}
}
