#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 10;
ll a[MAXN];
ll ans;
int n;
void compute(ll l, ll r){
if(r - l <= ans) return;
if(l == -1) return;
if(l == r){
ans = max(ans, r - l);
return;
}
ll n_l1, n_r1, n_l2, n_r2;
if(r - l == 2){
MinMax(l + 1, r - 1, &n_l1, &n_r1);
if(n_l1 != -1){
ans = max({ans, r - n_l1, n_l1 - l});
} else ans = max(ans, r - l);
return;
}
ll m = (l + r) / 2;
MinMax(l + 1, m, &n_l1, &n_r1);
MinMax(m + 1, r - 1, &n_l2, &n_r2);
if(n_l1 == -1 && n_l2 == -1){
ans = max(ans, r - l);
} else if(n_l1 == -1){
ans = max({ans, n_l2 - l, r - n_r2});
} else if(n_l2 == -1){
ans = max({ans, r - n_r1, n_l1 - l});
} else ans = max({ans, r - n_r2, n_l2 - n_r1, n_l1 - l});
compute(n_l1, n_r1);
compute(n_l2, n_r2);
}
ll findGap(int t, int n){
ll cur_s = 0, cur_t = 1e18;
ll mn, mx;
MinMax(cur_s, cur_t, &mn, &mx);
ans = 0;
compute(mn, mx);
return ans;
}
