#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
vector <ll> a;
ll findGap(int t, int n){
if (t == 1){
ll l = 0, r = INF;
while (l <= r && n > 0){
ll mn, mx;
MinMax(l, r, &mn, &mx);
if (mn == -1 && mx == -1)
break;
a.push_back(mn);
n--;
if (mx != mn){
a.push_back(mx);
n--;
}
l = mn + 1;
r = mx - 1;
}
ll res = 0;
sort(a.begin(), a.end());
for(int i = 1; i < (int) a.size(); i++)
res = max(res, a[i] - a[i - 1]);
return res;
} else {
ll l, r, d, res;
MinMax(0, INF, &l, &r);
res = (r - l - n) / n;
d = (r - l) / n;
a.push_back(l);
a.push_back(r);
l++;
r--;
while (l <= r){
ll mn, mx;
MinMax(l, min(l + d, r), &mn, &mx);
if (mn != -1 && mx != -1){
a.push_back(mn);
a.push_back(mx);
}
l += d + 1;
}
sort(a.begin(), a.end());
for(int i = 1; i < (int) a.size(); i++)
res = max(res, a[i] - a[i - 1]);
return res;
}
}
