#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
long long findGap(int T, int n){
if(T == 1){
vector<ll>a(n);
ll ans = 0, low = 0, high = 1e18;
int l = 0, r = n - 1;
while(l <= r){
MinMax(low, high, &a[l], &a[r]);
low = a[l++] + 1;
high = a[r--] - 1;
}
for(int i = 1; i < n; i++){
maximize(ans, a[i] - a[i - 1]);
}
return ans;
}
ll a_1, a_n;
MinMax(0, 1e18, &a_1, &a_n);
ll average = (a_n - a_1 + n - 2) / (n - 1), ans = average;
for(ll i = a_1; i <= a_n; i += average + 1){
ll x, y;
MinMax(i, min(i + average, a_1), &x, &y);
if(x != -1){
maximize(ans, x - a_1);
a_1 = y;
}
}
return ans;
}
