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