#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
const int maxn = 5e5+10;
const ll LINF = (ll)2e18;
ll ans=1,mn,mx,nn;
set<ll> S;
void query(ll l, ll r, ll &mn, ll &mx){
if(l<=r) MinMax(l,r,&mn,&mx);
else mn=-1,mx=-1;
}
void dnc(ll l, ll r){
S.insert(l), S.insert(r);
if(sz(S)==nn) return;
ll mid = (l+r)/2ll, l2, r2, l3, r3;
query(l+1,mid,l2,r2);
if(l2!=-1) ans = max(ans, l2-l);
if(l2!=-1 and r2!=-1) dnc(l2, r2);
query(mid+1,r-1,l3,r3);
if(r3!=-1) ans = max(ans, r-r3);
if(l3!=-1 and r3!=-1) dnc(l3, r3);
if(r2!=-1 and l3!=-1) ans = max(ans, l3-r2);
if(l2!=-1) S.insert(l2);
if(l3!=-1) S.insert(l3);
if(r2!=-1) S.insert(r2);
if(r3!=-1) S.insert(r3);
}
ll findGap(int T, int n)
{
ll s=0, t=LINF; ans=1; S.clear(); nn=n;
if(T==1){
vector<ll> v; v.clear(); int x = (n+1)/2;
while(x--) MinMax(s,t,&mn,&mx), v.pb(mn), v.pb(mx), s=mn+1, t=mx-1;
sort(all(v));
for(int i = 0; i < sz(v)-1; i++)
ans = max(ans, v[i+1]-v[i]);
return ans;
}
MinMax(s,t,&mn,&mx), dnc(mn,mx);
if(sz(S)==n){
while(sz(S)>1){
auto itr = S.begin(); auto itr2 = itr; itr2++;
ans = max(ans, *itr2-*itr); S.erase(S.begin());
}
}
return ans;
}
