#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long findGap(int T, int N) {
if (T == 1) {
vector <ll> v;
ll ret = 0;
ll L = 0, R = 1e18;
while ((ll)v.size() < N && L <= R) {
MinMax(L, R, &L, &R);
v.push_back(L);
if (L != R) v.push_back(R);
L++, R--;
}
sort(v.begin(), v.end());
for (int i = 1; i < (ll)v.size(); i++) ret = max(ret, v[i]-v[i-1]);
return ret;
}
ll L = 0, R = 1e18;
MinMax(L, R, &L, &R);
ll sz = R-L+1;
ll block = (sz+N-2)/(N-1);
ll lst = -1, ret = 0;
while (L <= R) {
// query dari L..L+block-1
ll MN, MX;
MinMax(L, L+block-1, &MN, &MX);
if (lst != -1) {
ret = max(ret, MN-lst);
}
if (MX == R) {
ret = max(ret, MX-MN);
}
if (MX != -1) {
lst = MX;
}
L += block;
}
return ret;
}
