#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
#define M (ll)(1e18)
using namespace std;
ll _A[100020];
long long findGap(int T, int n)
{
if(T == 2)
{
ll a, b, answer;
MinMax(0, M, &a, &b);
ll gap = (b - a) / (n - 1);
if((b - a) % (n - 1) != 0)
gap ++;
answer = gap - 1;
ll pre = a;
ll l = a - gap + 1;
ll r = a;
for(ll i = 0; r + 1 < b; ++ i)
{
l += gap;
r += gap;
r = min(b - 1, r);
ll x, y;
if(l > r)
{
break;
}
MinMax(l, r, &x, &y);
if(x == -1)
continue;
answer = max(answer, x - pre);
pre = y;
}
answer = max(b - pre, answer);
return answer;
}
int l, r;
_A[0] = -1;
l = 0; r = n + 1;
_A[r] = M + 1;
l ++; r --;
while(l <= r)
{
MinMax(_A[l - 1] + 1, _A[r + 1] - 1, &_A[l], &_A[r]);
l ++;
r --;
}
ll answer = 0;
for(int i = 2; i <= n; ++ i)
answer = max(answer, _A[i] - _A[i - 1]);
return answer;
}
