#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi22/d2/debug.h"
#else
#define debug(...) void(37)
#endif
long long findGap(int T, int N) {
debug(T, N);
long long first = -1;
long long last = -1;
const long long inf = (long long) 1e18;
MinMax(0, inf, &first, &last);
long long ans = (last - first + N - 2) / (N - 1);
if (N == 1) {
return 0;
} else if (T == 1) {
long long L = first, R = last;
for (int i = 0; i < (N - 1) / 2; ++i) {
long long next_L = -1, next_R = -1;
MinMax(L + 1, R - 1, &next_L, &next_R);
ans = max({ans, next_L - L, R - next_R});
L = next_L, R = next_R;
}
ans = max(ans, R - L);
} else {
long long cur = first;
while (cur != last) {
long long mn = -1, mx = -1;
long long ask = -1;
while (mn == -1) {
ask = (ask == -1 ? ans : min(ask * 2, last - cur));
MinMax(cur + 1, cur + ask, &mn, &mx);
debug(mn, mx);
}
ans = max(ans, mn - cur);
cur = mx;
}
}
return ans;
}
