#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
ll a[maxn];
long long findGap(int T, int n)
{
if(T == 1)
{
ll l = 0 , r = 1e18;
for(int i = 0; i < (n + 1) / 2; i++)
{
ll x , y;
MinMax(l , r , &x , &y);
a[i] = x;
a[n - i - 1] = y;
l = x + 1 , r = y - 1;
}
ll res = 0;
for(int i = 1; i < n; i++)
res = max(res , a[i] - a[i - 1]);
return res;
}
ll l ,r;
MinMax(1LL , 1000000000LL * 1000000000 , &l , &r);
ll res = (r - l + n - 2) / (n - 1);
ll a = l;
l++;
while(l < r)
{
ll s , t;
MinMax(l , l + res , &s , &t);
if(s == -1)
{
l += res + 1;
continue;
}
res = max(res , s - a);
a = t;
l = t + 1;
}
return res;
}
