#include "gap.h"
#include <vector>
#include <iostream>
using namespace std;
typedef long long llg;
vector<llg> a;
llg s1(int n)
{
a.resize(n);
llg x = 0, y = (llg)(1e18);
int d = 0, f = n-1;
while (d <= f) {
MinMax(x, y, &x, &y);
a[d] = x;
a[f] = y;
++x; ++d;
--y; --f;
}
llg r = 0;
for (int i = 0; i < (n-1); ++i) {
r = max(r, a[i+1] - a[i]);
}
return r;
}
llg s2(int n)
{
llg amin, amax;
MinMax(0, (llg)(1e18), &amin, &amax);
llg totSize = amax-amin+1-2;
llg sizeBloc = totSize/(n-1);
llg deb = 0, fin = amin;
llg ans = 0, der = amin;
for (int iBloc = 0; iBloc < (n-1); ++iBloc) {
deb = fin+1;
fin = deb+sizeBloc-1;
if (iBloc <= (totSize) % (n-1)) ++fin;
llg xl, xr;
MinMax(deb, fin, &xl, &xr);
if (xl != -1) {
if (der != -1) ans = max(ans, xl - der);
der = xr;
}
}
ans = max(ans, amax - der);
return ans;
}
llg findGap(int t, int n)
{
if (t == 1) return s1(n);
else return s2(n);
}
