#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long findGap(int T, int N) {
if (T == 1) {
ll A[N+1];
ll L = 0, R = 1e18;
for (int i = 1; i <= ceil(N/2.0); i++) {
ll P, Q;
MinMax(L, R, &P, &Q);
A[i] = P;
A[N-i+1] = Q;
L = P+1, R = Q-1;
}
ll mx = 0;
for (int i = 1; i < N; i++) mx = max(mx, A[i+1] - A[i]);
return mx;
} else {
ll L, R;
MinMax(0, 1e18, &L, &R);
ll sz = ceil((double) (R-L) / (N - 1));
ll rc = LLONG_MAX, mx = sz;
for (ll i = L; i <= R; i += sz+1) {
ll P, Q;
MinMax(i, i+sz, &P, &Q);
if (P > -1) mx = max(mx, P - rc), rc = Q;
}
return mx;
}
}
