#include "gap.h"
#include <algorithm>
const long long N = 1000000000000000000;
long long task1(int n)
{
long long l = 0, r = N, ans = 0;
for (int i = 0; i * 2 < n; ++i) {
long long ll, rr;
MinMax(l, r, &ll, &rr);
if (l) ans = std::max(ans, ll - l + 1);
if (r != N) ans = std::max(ans, r - rr + 1);
if (i * 2 == n - 2) ans = std::max(ans, rr - ll);
l = ll + 1;
r = rr - 1;
}
return ans;
}
inline long long d(int n, int k, long long l, long long r)
{
return l + (__int128)(r - l) * k / n;
}
long long task2(int n)
{
long long l, r;
MinMax(0, N, &l, &r);
if (n == 2) return r - l;
++l;
long long pr = l - 1, ans = 0, len = d(n - 2, 1, l, r) - d(n - 2, 0, l, r);
for (int i = 0; i < n - 2; ++i) {
long long ll, rr;
MinMax(d(n - 2, i, l, r), d(n - 2, i + 1, l, r) - 1, &ll, &rr);
if (ll != -1) {
ans = std::max(ans, ll - pr);
pr = rr;
}
}
return std::max(ans, r - pr);
}
long long findGap(int t, int n)
{
if (t == 1) return task1(n);
return task2(n);
}
