#include "gap.h"
#include <vector>
#include <deque>
#include <algorithm>
const long long INF = 1e18;
long long findGap(int T, int N)
{
if(T == 2) {
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;
}
std::vector <long long> firstValues, lastValues;
long long boundL = 0, boundR = INF;
for(int i = 1; i <= N / 2; i++) {
long long mn, mx;
MinMax(boundL, boundR, &mn, &mx);
firstValues.push_back(mn);
lastValues.push_back(mx);
boundL = mn + 1;
boundR = mx - 1;
}
if(N % 2 == 1) {
long long mn, mx;
MinMax(boundL, boundR, &mn, &mx);
firstValues.push_back(mn);
}
std::reverse(lastValues.begin(), lastValues.end());
for(long long val : lastValues) {
firstValues.push_back(val);
}
long long dif = 0;
for(int i = 1; i < (int)firstValues.size(); i++) {
dif = std::max(dif, firstValues[i] - firstValues[i - 1]);
}
return dif;
}
