#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long findGap(int T, int N)
{
if(T == 1)
{
long long mn = 0, mx = INF;
vector<long long> a(N);
int l = 0, r = N - 1;
while(l <= r)
{
MinMax(mn, mx, &mn, &mx);
// cout << "mn = " << mn << ", mx = " << mx << "\n";
a[l++] = mn;
a[r--] = mx;
mn += 1;
mx -= 1;
}
long long diff = 0;
for(int i = 1; i < N; i++)
{
diff = max(diff, a[i] - a[i - 1]);
}
return diff;
}
long long mn = 0, mx = INF;
MinMax(mn, mx, &mn, &mx);
long long min_diff = (mx - mn) / (N - 1) + 1;
long long ans = 0, prev = -INF;
for(long long i = mn; i <= mx; i += min_diff)
{
long long l, r;
MinMax(i, i + min_diff - 1, &l, &r);
if(l == -1)
{
continue;
}
if(prev == -INF)
{
prev = l;
}
ans = max(ans, l - prev);
ans = max(ans, r - l);
prev = r;
}
return ans;
}
