#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010], mx;
vector <ll> s;
int n, val, cnt = 2;
void search(int lo, int hi)
{
int m = (lo+hi)/2;
if(cnt == n || lo > hi)
return;
ll one,two;
MinMax(lo,hi,&one,&two);
if(one != -1)
s.push_back(one),cnt++;
if(two != -1 && two != one)
s.push_back(two),cnt++;
search(one+1,m);
search(m+1,two-1);
}
long long findGap(int T, int N)
{
n = N;
val = n % 2 ? n/2+1 : n/2;
if(T == 1)
{
MinMax(0,1e18,a,a + n-1);
for(int i = 1; i < val; i++)
MinMax(a[i-1]+1,a[n-i]-1,a + i,a + n-1-i);
for(int i = 0; i < n-1; i++)
mx = max(mx,a[i+1]-a[i]);
}
else if(T == 2)
{
ll fir,sec;
MinMax(0,1e18,&fir,&sec);
s.push_back(fir),s.push_back(sec);
search(fir+1,sec-1);
sort(s.begin(),s.end());
for(int i = 0; i < n-1; i++)
mx = max(mx,s[i+1]-s[i]);
}
return mx;
}
