#include "gap.h"
#include <iostream>
#define ll long long
const ll MN = 0, MX = 1e18;
using namespace std;
ll ret = MN;
ll ar[100001];
ll findGap(int T, int N)
{
if (T == 1)
{
ll L = MN, R = MX, k = 0;
for (int i = N; i > 0; i -= 2)
{
MinMax(L, R, &ar[k], &ar[N - 1 - k]);
L = ar[k] + 1;
R = ar[N - 1 - k] - 1;
k++;
}
for (int i = 1; i < N; i++) {ret = max(ret, ar[i] - ar[i - 1]);}
}
else
{
ll lf, rg, gp;
MinMax(MN, MX, &lf, &rg);
ret = (rg - lf + N - 2) / (N - 1), gp = ret;
ll pv = -1;
for (ll i = lf; i <= rg; i += gp + 1)
{
ll t1, t2;
MinMax(i, min(i + gp, rg), &t1, &t2);
if (t1 != -1)
{
if (pv != -1) {ret = max(ret, t1 - pv);}
pv = t2;
}
}
}
return ret;
}
