#include "gap.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;
// MinMax(, , &, &);
ll best;
void upd(ll x)
{
best = max(best, x);
}
long long findGap1(int N)
{
ll mini = -1, maxi = 1e18 + 79;
vector<ll> v(N);
for (int l = 0, r = N - 1; l <= r; l++, r--)
{
mini++, maxi--;
MinMax(mini, maxi, &mini, &maxi);
v[l] = mini;
v[r] = maxi;
}
ll ans = 0;
for (int i = 0; i < N - 1; i++) ans = max(ans, v[i + 1] - v[i]);
return ans;
}
long long findGap(int T, int N)
{
if (T == 1)return findGap1(N);
ll mini = -1, maxi = 1e18; best = 1;
set<ll> s;
set<pair<ll, pair<ll, ll> >, greater<pair<ll, pair<ll, ll> >> > pq;
MinMax(mini, maxi, &mini, &maxi);
s.insert({ mini, maxi });
pq.insert({ maxi - mini, {mini, maxi} });
while (!pq.empty())
{
ll dist = pq.begin()->first;
if (dist <= best) return best;
mini = pq.begin()->second.first;
maxi = pq.begin()->second.second;
if (mini + 1 == maxi) break;
if (mini + 2 == maxi)
{
ll a;
MinMax(mini + 1, maxi - 1, &a, &a);
if (a == -1) upd(2);
else upd(1);
break;
}
pq.erase(pq.begin());
ll m1 = (mini + maxi) / 2, m2 = (mini + maxi) / 2 + 1;
ll mi1, mx1, mi2, mx2;
MinMax(mini + 1, m1, &mi1, &mx1);
MinMax(m2, maxi - 1, &mi2, &mx2);
if (mi1 != -1) s.insert(mi1), s.insert(mx1);
if (mi2 != -1) s.insert(mi2), s.insert(mx2);
upd(*next(s.find(mini)) - mini);
upd(maxi - *prev(s.find(maxi)));
if (mx1 != -1 && mi2 != -1) upd(mi2 - mx1);
pq.insert({ mx1 - mi1, {mi1, mx1} });
pq.insert({ mx2 - mi2, {mi2, mx2} });
}
return best;
}
