#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 >= 0;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;
}
ll l, r;
MinMax(0, 1e18, &l, &r);
ll bl = (r - l) / (N - 1) + ((r - l) % (N - 1) != 0);
ll ans = bl;
for (ll i = l, pre = -1;i <= r;i += bl + 1) {
ll x = i, y = i + bl, a, b;
MinMax(x, y, &a, &b);
if (a != -1) {
if (pre != -1) ans = max(ans, a - pre);
pre = b;
}
}
return ans;
}
