#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const ll N = 1e18;
ll a[MAXN];
vector<ll> num;
ll solve(int n) {
ll l = 0, r = N, mi, ma;
for (int i = 0; i < (n + 1) / 2; i++) {
MinMax(l, r, &mi, &ma);
a[i] = mi;
a[n - 1 - i] = ma;
l = mi + 1;
r = ma - 1;
}
ll res = 0;
for (int i = 1; i < n; i++)
res = max(res, a[i] - a[i - 1]);
return res;
}
ll findGap(int t, int n) {
if (t == 1)
return solve(n);
ll res = 0, b, e, mi, ma;
MinMax(0, N, &b, &e);
num.push_back(b);
if (e - b - 1 < n) {
for (int i = b + 1; i < e; i++) {
MinMax(i, i, &mi, &ma);
if (mi != -1)
num.push_back(i);
}
num.push_back(e);
for (int i = 1; i < n; i++)
res = max(res, num[i] - num[i - 1]);
return res;
}
ll cnt = b + 1, x = (e - b - 1) / n, y = (e - b - 1) % n;
for (int i = 0; i < n; i++) {
ll r = cnt + (i < y? x + 1: x);
MinMax(cnt, r - 1, &mi, &ma);
if (mi != -1) {
num.push_back(mi);
num.push_back(ma);
}
cnt = r;
}
num.push_back(e);
for (int i = 1; i < num.size(); i++)
res = max(res, num[i] - num[i - 1]);
return res;
}
