#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000000;
ll findGap(int T, int N) {
if (T == 1) {
ll v[N], mn = -1, mx = INF+1;
for (int i = 0, k = N-1; i <= k; i++, k--) {
MinMax(mn+1, mx-1, &v[i], &v[k]);
mn = v[i];
mx = v[k];
}
ll ans = 0;
for (int i = 1; i < N; i++) {
ans = max(ans, v[i] - v[i-1]);
}
return ans;
} else {
ll total_min, total_max;
MinMax(0, INF, &total_min, &total_max);
ll ans = (total_max - total_min + ll(N - 1))/ll(N);
ll cur = total_min;
while(cur < total_max) {
ll mn = -1, mx = -1;
ll step = ans;
while (mn == -1) {
MinMax(cur+1, cur+step+1, &mn, &mx);
step += ans;
}
ans = max(ans, mn - cur);
cur = mx;
}
return ans;
}
}
