#include "gap.h"
long long findGap(int T, int N) {
long long a[N + 5], ln = 0;
long long l = 0, r = 1000000000000000000LL;
if (T == 1) {
int i = 0, j = N - 1;
while (i <= j) {
MinMax(l, r, &a[i], &a[j]);
l = a[i] + 1;
r = a[j] - 1;
i++;
j--;
}
ln = N;
} else {
MinMax(l, r, &l, &r);
long long len = (r - l - 1) / (N - 1);
long long ad = (r - l - 1) % (N - 1);
a[ln++] = l;
long long x, y;
l++;
for (int i = 0; i < N - 1; i++) {
long long lx = len + ((i < ad) ? 1 : 0);
MinMax(l, l + lx - 1, &x, &y);
l += lx;
if (x >= 0) {
a[ln++] = x;
a[ln++] = y;
}
}
a[ln++] = r;
}
long long result = 0;
for (int i = 1; i < ln; i++) {
long long maybe = a[i] - a[i - 1];
if (maybe > result) result = maybe;
}
return result;
}
