#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
long long solve1(int n)
{
vector<long long> v(n, 0);
long long x, y;
MinMax(0, inf, &x, &y);
if (n == 2) return y - x;
int ptrL = 0, ptrR = n - 1;
v[ptrL++] = x;
v[ptrR--] = y;
for (int i = 1; i < (n + 1) / 2; ++i)
{
MinMax(x + 1, y - 1, &x, &y);
v[ptrL++] = x;
v[ptrR--] = y;
}
long long ans = 0;
for (int i = 1; i < n; ++i)
{
ans = max(ans, v[i] - v[i - 1]);
}
return ans;
}
long long findGap(int T, int N)
{
if (T == 1)
{
return solve1(N);
}
int n = N;
long long a, b;
MinMax(0, inf, &a, &b);
if (n == 2)
{
return b - a;
}
long long step = (b - a) / (1LL * (n - 1)) + 1;
long long last = a, ans = step - 1;
for (long long i = a; i <= b; i += step)
{
long long x, y;
MinMax(i, i + step - 1, &x, &y);
if (x == -1) continue;
ans = max(ans, x - last);
last = y;
}
return ans;
}
