#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
if (T == 1)
{
ll l = 0, r = 1E18, mn, mx;
vector<ll> v;
while (l < r)
{
MinMax(l, r, &mn, &mx);
v.push_back(mn);
v.push_back(mx);
l = mn + 1;
r = mx - 1;
}
ll gap = 0;
if (l == r)
{
v.push_back(r);
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size() - 1; i++)
{
gap = max(v[i + 1] - v[i], gap);
}
return gap;
}
vector<pair<ll, ll>> segment;
ll mn, mx;
MinMax(0, 1E18, &mn, &mx);
ll s = (mx - mn) / (N - 1), rm = (mx - mn) % (N - 1);
if (mx - mn + 1 == N)
{
return 1;
}
mn++;
ll last_min = mn;
for (int i = 0; i < N - 1; i++)
{
ll l, r;
ll ql = last_min, qr = last_min + min(s + ((rm--) > 0) - 1, (ll)mx);
last_min = qr + 1;
MinMax(ql, qr, &l, &r);
if (l != -1)
{
segment.push_back({0, 0});
int j = segment.size() - 1;
segment[j].first = l;
segment[j].second = r;
}
}
ll mxdiff = -mn + segment[0].first + 1;
for (int i = 0; i < segment.size() - 1; i++)
{
mxdiff = max(segment[i + 1].first - segment[i].second, mxdiff);
}
return mxdiff;
}
