#include "gap.h"
#include <vector>
long long findGap(int T, int N)
{
if (T == 1) {
std::vector<long long> arr(N);
long long l = 0, r = (long long) 1e18;
long long min_v, max_v;
for (int i = 0; i < (N + 1) / 2; ++i) {
MinMax(l, r, &min_v, &max_v);
// assert(min_v != -1 && max_v != -1);
arr[i] = min_v;
arr[N - i - 1] = max_v;
l = min_v + 1;
r = max_v - 1;
}
long long ans = -1;
for (int i = 0; i < N - 1; ++i) {
ans = std::max(ans, arr[i + 1] - arr[i]);
}
return ans;
} else {
long long min_v, max_v;
MinMax(0, (long long) 1e18, &min_v, &max_v);
long long range = max_v - min_v;
long long S = (range + N - 2) / (N - 1);
long long ans = 0;
long long prev = min_v;
for (long long i = min_v; i < max_v; i += S + 1) {
long long cur_min, cur_max;
MinMax(i, i + S, &cur_min, &cur_max);
if (cur_min != -1) {
ans = std::max(ans, cur_min - prev);
prev = cur_max;
}
}
return ans;
}
}
