#include "gap.h"
#include <cassert>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iostream>
using namespace std;
long long findGap(int T, int N)
{
long long L, R;
long long X = 1e18;
MinMax(0, X, &L, &R);
long long maxGap = (R - L + N - 2) / (N - 1);
if (N == 2) return R - L;
if (T == 2) {
while (R - L > maxGap) {
long long gap = maxGap;
while (true) {
long long A, B;
MinMax(L + 1, L + gap + 1, &A, &B);
if (A == -1) { gap *= 2; continue; }
if (maxGap < A - L) maxGap = A - L;
L = B;
break;
}
}
} else {
for (int i = N - 2; i > 0; i -= 2) {
long long A, B;
MinMax(L + 1, R - 1, &A, &B);
if (maxGap < A - L) maxGap = A - L;
if (maxGap < R - B) maxGap = R - B;
L = A, R = B;
}
if (maxGap < R - L) maxGap = R - L;
}
return maxGap;
}
