#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
set<long long> a;
void solve(long long min_val, long long max_val)
{
if(min_val > max_val)
{
return;
}
long long mn, mx;
MinMax(min_val, max_val, &mn, &mx);
if(mn == -1)
{
return;
}
a.insert(mn);
a.insert(mx);
if(mn == mx)
{
return;
}
min_val = mn + 1;
max_val = mx - 1;
long long mid = (min_val + max_val) / 2;
solve(min_val, mid);
solve(mid + 1, max_val);
}
long long findGap(int T, int N)
{
if(T == 1)
{
long long mn = 0, mx = 1e18;
vector<long long> a(N);
int l = 0, r = N - 1;
while(l <= r)
{
MinMax(mn, mx, &mn, &mx);
// cout << "mn = " << mn << ", mx = " << mx << "\n";
a[l++] = mn;
a[r--] = mx;
mn += 1;
mx -= 1;
}
long long diff = 0;
for(int i = 1; i < N; i++)
{
diff = max(diff, a[i] - a[i - 1]);
}
return diff;
}
long long mn = 0, mx = 1e18;
long long mid = (mn + mx) / 2;
solve(mn, mid);
solve(mid + 1, mx);
long long diff = 0;
long long prev = *(a.begin());
for(auto i: a)
{
diff = max(diff, i - prev);
prev = i;
}
return diff;
}
