#include "gap.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int inf = 1e18,MOD = 998244353,B = 250;
int findGap(int32_t T, int32_t N)
{
int ans = 0;
int l,r;
int* lp = &l,*rp = &r;
int u = 0,v = inf;
MinMax(u,v,lp,rp);
int son = *rp,bas = *lp;
if (T == 2) {
int L = son-bas;
int x = (L+N-2)/(N-1);
int sonlst = bas;
for (int i = bas+1;i<=son;i+=x) {
MinMax(i,i+x-1,lp,rp);
if (*lp != -1) ans = max(ans,*lp-sonlst);
if (*rp != -1) sonlst = *rp;
}
return ans;
}
else {
vi arr(N);
int ptr = 0,ptr2 = N-1;
arr[ptr++] = *lp;
arr[ptr2--] = *rp;
while (ptr <= ptr2) {
MinMax(arr[ptr-1]+1,arr[ptr2+1]-1,lp,rp);
arr[ptr++] = *lp;
arr[ptr2--] = *rp;
}
for (int i=0;i<N-1;i++) ans = max(ans,arr[i+1]-arr[i]);
return ans;
}
}
