#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << '\n'
using namespace std;
const ll INF = 1e18;
ll findGap(int T, int N)
{
ll ans = 0;
if (T == 1)
{
vector<ll> a;
ll l = 1, r = INF;
while (a.size() < N)
{
ll mn = INF, mx = -INF;
MinMax(l, r, &mn, &mx);
if (mn == -1)
break;
a.push_back(mn);
a.push_back(mx);
l = mn + 1;
r = mx - 1;
}
sort(a.begin(), a.end());
for (int i = 0; i < a.size() - 1; i++)
ans = max(ans, a[i + 1] - a[i]);
}
else
{
ll st = INF, en = -INF;
MinMax(0, INF, &st, &en);
ll X = (en - st + N - 2) / (N - 1);
ll x = st;
ll premx = -1;
// cout << en - st + 1 << ' ' << X << endl;
ans = X;
int cnt = 0;
while (x <= en)
{
cnt++;
ll mn = INF, mx = -INF;
ll nxx = x + X;
MinMax(x, nxx, &mn, &mx);
// cout << x << ' ' << nxx << ' ' << mn << ' ' << mx << endl;
if (premx != -1 && mx != -1)
ans = max(ans, mn - premx);
if (mx != -1)
premx = mx;
// cout << x << ' ' << nxx << endl;
x = nxx + 1;
}
}
return ans;
}
