#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long findGap(int T, int N) {
if (T == 1) {
ll A[N+1];
ll L = 0, R = 1e18;
for (int i = 1; i <= ceil(N/2.0); i++) {
ll P, Q;
MinMax(L, R, &P, &Q);
A[i] = P;
A[N-i+1] = Q;
L = P+1, R = Q-1;
}
ll mx = 0;
for (int i = 1; i < N; i++) mx = max(mx, A[i+1] - A[i]);
return mx;
} else {
vector <ll> A;
function <void(ll, ll)> rc = [&] (ll L, ll R) {
if (L == -1 || R == -1 || R < L) return;
if (L == R) { A.emplace_back(L); return; }
ll x = L + (R-L)/2;
ll P1, Q1, P2, Q2;
MinMax(L, x, &P1, &Q1), MinMax(x+1, R, &P2, &Q2);
if (P1 > -1) A.emplace_back(P1);
rc(P1+1, Q1-1);
if (P1 != Q1 && Q1 > -1) A.emplace_back(Q1);
if (P2 > -1) A.emplace_back(P2);
rc(P2+1, Q2-1);
if (P2 != Q2 && Q2 > -1) A.emplace_back(Q2);
};
rc(0, (ll) 1e18);
ll mx = 0;
for (int i = 0; i < N-1; i++) mx = max(mx, A[i+1] - A[i]);
return mx;
}
}
