#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cdiv(ll a, ll b){
return (a + b - 1) / b;
}
ll findGap(int T, int N){
if (T == 1){
vector<ll> vec(N);
ll lv = 0, rv = 1e18, ans = 0;
for (int l = 0, r = N - 1; l <= r; l++, r--){
MinMax(lv, rv, &vec[l], &vec[r]);
lv = vec[l] + 1; rv = vec[r] - 1;
}
for (int i = 1; i < N; i++) ans = max(ans, vec[i] - vec[i - 1]);
return ans;
}
else{
ll mn, mx; MinMax(0, 1e18, &mn, &mx);
ll gap = cdiv(mx - mn, N - 1), prv = mn, ans = 0;
for (int i = 0; i < N - 1; i++){
ll mnh, mxh; MinMax(min(mn + gap * i + 1, mx), min(mn + gap * (i + 1), mx), &mnh, &mxh);
if (mnh == -1) continue;
ans = max(ans, mnh - prv);
prv = mxh;
}
return ans;
}
}
