#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'
ll findGap(int t, int n){
if(t == 1){
vector<ll> vl, vr;
ll l = 0, r = 1e18, cnt = 0, ans = 0;
while(cnt < n){
ll mn = l, mx = r;
MinMax(l, r, &mn, &mx);
if(mn == -1) break;
if(!vl.empty()) ans = max(ans, mn - vl.back());
vl.push_back(mn);
cnt++;
if(mn == mx) break;
if(!vr.empty()) ans = max(ans, vr.back() - mx);
vr.push_back(mx);
cnt++;
l = mn+1;
r = mx-1;
}
ans = max(ans, vr.back() - vl.back());
return ans;
}
ll mn, mx;
MinMax(0, 1e18, &mn, &mx);
ll g = (mx-mn-1)/(n-1) + 1;
ll ans = g, p = mn, maxi = mx;
for(int i = mn+1; i < maxi; i += g+1){
MinMax(i, min(i+g, maxi-1), &mn, &mx);
ans = max(ans, mn - p);
p = mx;
}
ans = max(ans, maxi - p);
return ans;
}
