#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;
long long findGap(int t, int n)
{
if(t == 1){
ll mn, mx;
MinMax(0, inf, &mn, &mx);
vector<ll>a(n + 1);
a[1] = mn, a[n] = mx;
for(int i = 2; i * 2 - 1 <= n; i++){
MinMax(a[i - 1] + 1, a[n - i + 2] - 1, &mn, &mx);
a[i] = mn;
a[n - i + 1] = mx;
}
ll ans = 0;
for(int i = 2; i <= n; i++){
ans = max(ans, a[i] - a[i - 1]);
}
return ans;
}
else{
ll mn, mx;
MinMax(0, inf, &mn, &mx);
ll siz = (mx - mn + n - 2) / (n - 1);
ll prv = mn, ans = 0;
for(ll i = mn + 1; i <= mx; i += siz){
ll r = min(i + siz - 1, mx), a, b;
MinMax(i, r, &a, &b);
ans = max(ans, a - prv);
prv = b;
}
ans = max(ans, mx - prv);
return ans;
}
}
