#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
set<long long> x;
int N;
void solve(long long l, long long r){
//cout << l << " " << r << "\n";
if(l > r || (int) x.size() == N) return;
long long mn, mx;
MinMax(l, r, &mn, &mx);
if(mn == -1 || mx == -1) return;
x.insert(mn);
x.insert(mx);
if(l == r) return;
solve(mn + 1, mx - 1);
//solve(mid + 1, mx - 1);
}
long long findGap(int T, int n)
{
N = n;
x.clear();
solve(0ll, (long long) 1e18 + 10);
long long ans = 0ll, prev = *x.begin();
for(auto it : x){
ans = max(ans, it - prev);
prev = it;
}
return ans;
}
