#include <bits/stdc++.h>
using namespace std;
#include "gap.h"
const long long inf = 1e18;
template<class U, class V>
bool maxz(U &a, V b) {
if (a < b) return a = b, 1;
return 0;
}
long long findGap(int T, int N) {
long long x, y;
MinMax(0, inf, &x, &y);
long long z = (y - x - 1) / (N - 1), t = (y - x - 1) % (N - 1);
vector<pair<long long, long long>> vv{pair<long long, long long>{0, x}};
long long l = x + 1;
for (int i = 1; i < N; i++) {
long long r = l + z + (i < t);
vv.push_back({l, r - 1});
// cerr << l << " " << r - 1 << "\n";
l = r;
}
vv.push_back({y, inf});
int m = vv.size();
vector<pair<long long, long long>> h(m, {-1, -1});
for (int i = 1; i + 1 < m; i++) {
MinMax(vv[i].first, vv[i].second, &x, &y);
h[i] = {x, y};
}
long long res = 0;
for (int l = 1, r = 1; l + 1 < m; l = r) {
for (; r + 1 < m && h[r] == h[l]; r++);
if (h[r].first == -1) {
long long gap = vv[r].first - vv[l - 1].second;
maxz(res, gap);
}
}
return res;
}
