#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
set<long long> a;
vector<long long> b;
void recur(long long l, long long r) {
if (r-l <= 1) {
long long tmpl, tmpr;
MinMax(l, r, &tmpl, &tmpr);
if (tmpl == -1) return;
a.insert(tmpl);a.insert(tmpr);
return;
}
long long m = l + (r-l)/2;
long long tmpl, tmpr;
MinMax(l, m-1, &tmpl, &tmpr);
if (tmpl != -1) {
a.insert(tmpl);a.insert(tmpr);
if (tmpl + 1 < tmpr) {
recur(tmpl+1, tmpr-1);
}
}
MinMax(m, r, &tmpl, &tmpr);
if (tmpl != -1) {
a.insert(tmpl);a.insert(tmpr);
if (tmpl + 1 < tmpr) {
recur(tmpl+1, tmpr-1);
}
}
}
long long findGap(int T, int N) {
if (T == 1) {
long long mn = 0, mx = 1e18;
for (int i=0;i<(N+1)/2;i++) {
long long tmn, tmx;
MinMax(mn, mx, &tmn, &tmx);
if (tmn == -1) break;
a.insert(tmn);
a.insert(tmx);
mn = tmn+1;mx = tmx-1;
}
}
else recur(0, (long long)1e18);
for (long long x:a)b.push_back(x);
long long dif = 0;
for (int i=1;i<N;i++) {
dif = max(dif, b[i] - b[i-1]);
}
return dif;
}
