#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
pll query(ll a, ll b) {
if (a>b) return mp(-1, -1);
ll x, y;
// printf("[%lld, %lld]\n", a, b);
MinMax(a, b, &x, &y);
return mp(x, y);
}
long long findGap(int T, int N) {
ll sol=0;
pll pp=query(0, 1e18);
ll MIN=pp.X, MAX=pp.Y;
if (T==1) {
N-=2;
while (N>=1) {
pll curr=query(pp.X+1, pp.Y-1);
if (curr.X==-1) break;
sol=max(sol, curr.X-pp.X);
sol=max(sol, pp.Y-curr.Y);
pp=curr;
N-=2;
}
sol=max(sol, pp.Y-pp.X);
}
else {
ll d=(MAX-MIN)/(N-1);
ll pr=MIN;
ll l=MIN, r=MIN;
while (r!=MAX) {
l=r+1; r=min(l+d, MAX);
pll ans=query(l, r);
if (ans.X!=-1) {
sol=max(sol, ans.X-pr);
pr=ans.Y;
}
if (r==MAX && ans.X!=-1) sol=max(sol, MAX-ans.Y);
}
}
return sol;
}
/*
1 8
1 5 9 18 32 46 55 63
*/
