#include "gap.h"
#include <vector>
const long long INF = 1e18;
long long findGap(int T, int N)
{
long long a0, aN;
MinMax(0LL, INF, &a0, &aN);
long long L = (aN - a0) / (N - 1);
if(N == 2) {
return L;
}
if((aN - a0) % (N - 1) != 0) {
++L;
}
std::vector <long long> values;
values.push_back(a0);
long long prevRightEnd = a0;
for(int i = 1; i <= N - 1; i++) {
long long mn, mx;
if(prevRightEnd + L - 1 < aN) {
MinMax(prevRightEnd + 1, prevRightEnd + L, &mn, &mx);
} else {
if(prevRightEnd + 1 <= aN - 1) {
MinMax(prevRightEnd + 1, aN - 1, &mn, &mx);
}
}
prevRightEnd = prevRightEnd + L;
if(mn != -1) {
values.push_back(mn);
if(mx != mn) {
values.push_back(mx);
}
}
}
values.push_back(aN);
long long dif = 0;
for(int i = 1; i < (int)values.size(); i++) {
dif = std::max(dif, values[i] - values[i - 1]);
}
return dif;
}
