#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long B[100005];
long long findGap(int T, int N)
{
if(T == 1){
long long ans = 0, mini, maxi;
B[N+1] = (long long)1e18 + 5, B[0] = -1;
int j = N;
for(int i=1;i<=j;i++){
//cout << B[i-1] << " " << B[j+1] << '\n';
MinMax(B[i-1]+1, B[j+1]-1, &mini, &maxi);
//cout << mini << '\n';
B[i] = mini, B[j] = maxi;
//cout << *mini << " " << *maxi << '\n';
j--;
}
for(int i=1;i<N;i++)ans = max(ans, B[i+1] - B[i]);
return ans;
}
else{
long long ans = 0, mini, maxi;
B[N+1] = (long long)1e18 +1;
queue<pair<long long, long long > > q;
q.push({0ll, B[N+1]});
vector<long long>v;
while(!q.empty()){
long long y = q.front().first, z = q.front().second;
q.pop();
//cout << y << " " << z << '\n';
long long m = (y + z)/2;
MinMax(y, m, &mini, &maxi);
if(mini != -1){
if(mini == maxi)v.push_back(mini);
else q.push({mini-1, maxi-1}), v.push_back(mini), v.push_back(maxi);
}
if(m == z)continue;
MinMax(m+1, z, &mini, &maxi);
if(mini != -1){
if(mini == maxi)v.push_back(mini);
else q.push({mini+1,maxi-1}), v.push_back(mini), v.push_back(maxi);
}
}
sort(v.begin(), v.end());
for(int i=0;i<v.size()-1;i++)ans = max(ans, v[i+1] - v[i]);
return ans;
}
return 0;
}
