#include <iostream>
#include "gap.h"
#define ll long long
using namespace std;
const ll M = 1e18;
ll l, r, z, p, a, b, sz, f;
long long findGap(int T, int N) {
MinMax(0, M, &a, &b);
if (T == 1) {
if (N == 2) return b-a;
l = a, r = b, f = -1e18;
for (int i=0; i<(N-1)/2; ++i) {
MinMax(l+1, r-1, &a, &b);
f = max(f, a-l);
f = max(f, r-b);
l = a, r = b;
}
return f;
}
l = a+1, r = b, p = a, f = -1e18;
sz = (b-a)/N;
f = sz;
while (l < r) {
z = min(r, l+sz);
MinMax(l, z, &a, &b);
l = z+1;
f = max(f, a-p);
if (b != -1) p = b;
}
return f;
}
