#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector <ll> dnc(ll l, ll r, ll need) {
need = min(need, r - l + 1);
if (need <= 0) return {};
if (need <= 2) {
vector <ll> res;
ll x, y; MinMax(l, r, &x, &y);
if (x != -1) res.emplace_back(x);
if (x < y) res.emplace_back(y);
return res;
}
ll mid = (l + r) >> 1;
vector <ll> A = dnc(l, mid, need);
vector <ll> B = dnc(mid + 1, r, need - A.size());
for (ll &x: B) A.emplace_back(x);
return A;
}
ll findGap(int T, int N) {
if (T == 1) {
vector <ll> A, B;
ll l = 0, r = 1e18;
while (l <= r && A.size() + B.size() < N) {
ll x, y; MinMax(l, r, &x, &y);
if (x == -1) break;
A.emplace_back(x);
if (x < y) B.emplace_back(y);
l = x + 1, r = y - 1;
}
for (int i = B.size() - 1; i > -1; i--)
A.emplace_back(B[i]);
ll ans = 0;
for (int i = 1; i < A.size(); i++)
ans = max(ans, A[i] - A[i - 1]);
return ans;
}
else {
vector <ll> res = dnc(0, 1e18, N);
ll ans = 0;
for (int i = 1; i < N; i++)
ans = max(ans, res[i] - res[i - 1]);
return ans;
}
}
