#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#include "gap.h"
const ll INF = 1e18;
ll x, y;
ll findGap(int T, int n){
ll ans = 0;
if(T == 1){
vector<ll> a, b;
ll low = 0, high = INF;
int done = 0;
while(done < n){
MinMax(low, high, &x, &y);
a.push_back(x);
++done;
if(x < y) b.push_back(y), ++done;
low = x + 1LL;
high = y - 1LL;
}
while(!b.empty()) a.push_back(b.back()), b.pop_back();
for(int i=1; i<n; ++i) ans = max(ans, a[i]-a[i-1]);
}else{
vector<pair<ll, ll>> a;
ll low, high;
MinMax(0, INF, &low, &high);
a.emplace_back(-1, low);
ll w = (high - low - 2LL) / ((ll)n - 1LL);
for(ll s=low+1; s<high; s+=w+1){
MinMax(s, s+w, &x, &y);
if(x >= 0) a.emplace_back(x, y);
}
a.emplace_back(high, -1);
for(int i=1; i<(int)a.size(); ++i) ans = max(ans, a[i].first - a[i-1].second);
}
return ans;
}
