#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000000LL;
ll a[100005];
long long findGap(int T, int N){
if(T == 1){
int l = 1, r = N;
a[N+1] = INF+1;
while(l <= r){
MinMax(a[l-1]+1, a[r+1]-1, &a[l], &a[r]);
l++;
r--;
}
ll res = 0;
for(int i=2; i<=N; i++) res = max(res, a[i]-a[i-1]);
return res;
}
ll mn, mx;
MinMax(1, INF, &mn, &mx);
ll block = (mx-mn+N-2)/(N-1);
ll res = block;
ll posl = mn;
ll i;
for(i=mn; i+block+1 <= mx; i += block+1){
ll a, b;
MinMax(i, i+block+1, &a, &b);
if(a == -1) continue;
res = max(res, a-posl);
posl = b;
}
ll a, b;
MinMax(i, mx, &a, &b);
if(a != -1) res = max(res, a-posl);
return res;
}
