#include <bits/stdc++.h>
//#include "grader.cpp"
#include "gap.h"
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pl pair < ll, ll >
#define pii pair < int, pl >
#define vii vector < pl >
const int MAXN = 1e5 + 7;
const ll INF = 1e18;
ll mn, mx, l, ans;
ll s, f, sz, r;
pl a[MAXN];
long long findGap(int T, int N){
if (T == 1){
l = 1, r = N, f = INF;
while (r >= l){
MinMax(s, f, &mn, &mx);
f = mx - 1;
s = mn + 1;
a[l].fr = mn; a[r].fr = mx;
l++; r--;
}
for (int i = 2; i <= N; i++)
ans = max(ans, a[i].fr - a[i - 1].fr);
}
else {
MinMax(0, INF, &s, &f);
sz = (f - s - 1) / (N - 1);
r = (f - s - 1) % (N - 1);
a[1] = {s, s};
a[N + 1] = {f, f};
l = s + 1;
for (int i = 2; i <= N; i++){
if (r){
r--;
MinMax(l, l + sz, &mn, &mx);
if (mn != -1)
a[i] = {mn, mx};
else
a[i] = a[i - 1];
l = l + sz + 1;
}
else {
MinMax(l, l + sz - 1, &mn, &mx);
if (mn != -1)
a[i] = {mn, mx};
else
a[i] = a[i - 1];
l = l + sz;
}
ans = max(ans, a[i].fr - a[i - 1].sc);
}
ans = max(ans, a[N + 1].fr - a[N].sc);
}
return ans;
}
