#include "gap.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll ar[100010]; int tp;
ll mx, mn, gp;
priority_queue<ll, vector<ll>, greater<ll> > pq;
long long findGap(int T, int N)
{
if (T==1) {
mn=-1, mx=1000000000000000000ll+1ll;
int cnt=0;
for (int j=0; j<(N+1)/2; j++) {
if (mn+1>mx-1) break;
MinMax(mn+1, mx-1, &mn, &mx);
pq.push(mn); pq.push(mx);
cnt++;
}
gp=pq.top(); pq.pop();
mx=0;
while (!pq.empty()) {
mn=gp; gp=pq.top(); pq.pop();
mx=max(mx, gp-mn);
}
return mx;
}
MinMax(0, 1000000000000000000ll, &mn, &mx);
gp=(mx-mn+N-2)/(ll)(N-1);
ll n, x;
for (ll i=mn; i<mx; i+=gp) {
MinMax(i, min(i+gp-1, mx-1), &n, &x);
if (n==-1&&x==-1) continue;
if (n==x) ar[tp++]=n;
else {
ar[tp++]=n; ar[tp++]=x;
}
}
ar[tp++]=mx;
ll ans=0;
for (int j=0; j<tp-1; j++) ans=max(ans, ar[j+1]-ar[j]);
return ans;
}
