#include "gap.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
// void MinMax(ll l, ll r, ll &mn, ll &mx){
// cout << l <<" " << r << endl;
// cin >> mn >> mx;
// }
vector <ll> vec;
int nx;
void calc(ll l, ll r){
ll mn, mx;
MinMax(l, r, &mn, &mx);
if(mn == -1) return;
if(mn == mx){
vec.pb(mn);
return;
}
vec.pb(mn);
vec.pb(mx);
l = mn + 1;
r = mx - 1;
if((ll)vec.size() == nx) return;
calc(l, r);
}
long long findGap(int t, int n)
{
nx = n;
ll ans = 1;
if(t == 1){
calc(0, 1e18);
sort(vec.begin(), vec.end());
for(ll i = 0; i < (ll)vec.size() - 1; i++){
ans = max(ans, vec[i + 1] - vec[i]);
}
} else{
ll mn, mx, gr = (n - 1) / 2, prev, k, l = 0, r = 1e18;
MinMax(l, r, &mn, &mx);
if(n == 2) return mx - mn;
prev= mn;
l = mn + 1;
r = mx - 1;
k = (r - l + 1) / gr;
for(ll cur = l; cur <= r; cur = cur + k){
ll mnx, mxx;
MinMax(cur, min(cur + k - 1, r), &mnx, &mxx);
if(mnx != -1){
ans = max(ans, mnx - prev);
ans = max(ans, mxx - mnx);
prev = mxx;
}
}
ans = max(ans, mx -prev);
}
return ans;
}
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// ll t, n;
// cin >> t >> n;
// findGap(t, n);
// return 0;
// }
