#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXVAL = 1e18;
pair<ll, ll> query(ll l, ll r) {
ll a, b;
MinMax(l, r, &a, &b);
return make_pair(a, b);
}
ll findGap(int T, int N) {
auto [mi, mx] = query(0, MAXVAL);
if (N == 2) {
return mx-mi;
} else if (N <= 4) {
auto [a, b] = query(mi+1, mx-1);
return max({a-mi, b-a, mx-b});
}
ll query_range = (mx-mi+N)/N;
vector<pair<ll, ll>> ranges;
for (ll lb = mi; lb < mx; lb += query_range) {
auto [a, b] = query(lb, lb+query_range-1);
if (a != -1) {
ranges.emplace_back(a, b);
lb = b;
}
}
ll ans = 0;
for (int i = 0; i < ranges.size(); i++) {
ans = max(ans, ranges[i].second - ranges[i].first);
if (i > 0) ans = max(ans, ranges[i].first - ranges[i-1].second);
}
return ans;
}
