#include <bits/stdc++.h>
#include "gap.h"
#define endl '\n'
using namespace std;
const int MAX = (2e5) + 5;
long long a[MAX];
long long findGap(int T, int n)
{
if (T == 1)
{
long long l = 0, r = (1e18) + 1, s, t;
for (int i = 1; i <= (n + 1) / 2; i++)
{
MinMax(l, r, &s, &t);
a[i] = s;
a[n - i + 1] = t;
l = s + 1;
r = t - 1;
}
long long ans = 0;
for (int i = 2; i <= n; i++)
ans = max(ans, a[i] - a[i - 1]);
return ans;
}
long long s, t;
MinMax(1, (1e18), &s, &t);
long long x = (t - s + n - 2) / (n - 1);
long long ans = x, l, r, last = s;
for (long long i = s; i < t; i += x + 1)
{
if (i + x >= t)
MinMax(i, t, &l, &r);
else
MinMax(i, i + x, &l, &r);
if (l != -1)
{
ans = max(ans, l - last);
last = r;
}
}
return ans;
}
