#include <bits/stdc++.h>
#include "gap.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
ll ans;
ll mn, mx;
void solve(ll l, ll r){
if(ans > r - l + 2) return;
if(l == r) return;
ll d = r - l;
vector <ll> s;
for(int i = 0 ; i < 5 ; i++){
s.push_back(l + d / 5 * i);
}
s.push_back(r);
s.resize(unique(s.begin(), s.end()) - s.begin());
int sz = (int)s.size() - 1;
vector <ll> mnq, mxq;
for(int i = 0 ; i < sz ; i++){
MinMax(s[i], s[i + 1], &mn, &mx);
if(mn != -1){
mnq.push_back(mn);
mxq.push_back(mx);
}
}
if(mnq.size()){
ans = max(ans, mnq[0] - (l - 1));
ans = max(ans, r + 1 - mxq.back());
}
else ans = max(ans, r + 1 - (l - 1));
for(int i = 0 ; i + 1 < (int)mnq.size() ; i++){
ans = max(ans, mnq[i + 1] - mxq[i]);
}
for(int i = 0 ; i < (int)mnq.size() ; i++){
solve(mnq[i] + 1, mxq[i] - 1);
}
}
ll findGap(int T, int N){
if(T == 1) return 0;
MinMax(0, 1e18, &mn, &mx);
solve(mn + 1, mx - 1);
return ans;
}
