#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
pll ask(ll l, ll r) {
ll mn, mx;
MinMax(l, r, &mn, &mx);
return {mn, mx};
}
long long findGap(int T, int N) {
if (T == 1) {
vector<ll> a(N+1);
auto [l, r] = ask(1, 1e18);
int cur = 2;
a[1] = l, a[N] = r;
while (cur <= (N+1) / 2) {
auto [x, y] = ask(l+1, r-1);
a[cur] = x, a[N-cur+1] = y;
l = x, r = y, cur++;
}
ll mx = 0;
for (int i = 1; i <= N-1; i++) mx = max(mx, a[i+1] - a[i]);
return mx;
} else {
auto [l, r] = ask(1, 1e18);
ll d = (r - l + N - 2) / (N - 1);
ll p = l, mx = d;
for (ll i = l + 1; i <= r; i += d) {
auto [x, y] = ask(i, i + d - 1);
if (x == -1) continue;
mx = max(mx, x - p), p = y;
}
return max(mx, r - p);
}
}
