#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll findGap(int T, int N) {
if (T == 1 || N <= 2) {
vector <ll> A, B;
ll l = 0, r = 1e18;
while (l <= r && A.size() + B.size() < N) {
ll x, y; MinMax(l, r, &x, &y);
if (x == -1) break;
A.emplace_back(x);
if (x < y) B.emplace_back(y);
l = x + 1, r = y - 1;
}
for (int i = B.size() - 1; i > -1; i--)
A.emplace_back(B[i]);
ll ans = 0;
for (int i = 1; i < A.size(); i++)
ans = max(ans, A[i] - A[i - 1]);
return ans;
}
else {
ll l, r; MinMax(0, 1e18, &l, &r);
ll blockSize = (r - l) / (N - 1) + ((r - l) % (N - 1) != 0);
ll ans = blockSize;
for (ll i = l, pre = -1; i <= r; i += blockSize + 1) {
ll x = i, y = i + blockSize, a, b;
MinMax(x, y, &a, &b);
if (a != -1) {
if (pre != -1) ans = max(ans, a - pre);
pre = b;
}
}
return ans;
}
}
