#include "bits/stdc++.h"
#include "gap.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
const time_point start_time;
public:
Timer(): start_time(now()) {}
rep elapsed_time() const {
return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
}
} timer;
ll findGap(int t, int n) {
ll lb, rb, ans = 1;
MinMax(0, 1e18, &lb, &rb);
if (t == 2) {
ll mi = (rb - lb) / ll(n - 1) + ((rb - lb) % ll(n - 1) != 0);
ll pr = lb;
while (pr != rb) {
ll l, r;
MinMax(lb + 1, lb + mi, &l, &r);
if (l != -1) {
ans = max(ans, l - pr);
pr = r;
}
lb = lb + mi;
}
return ans;
}
ll cnt = n - 2;
while (true) {
if (cnt <= 0) {
ans = max(ans, rb - lb);
break;
}
ll l, r;
MinMax(lb + 1, rb - 1, &l, &r);
ans = max({ans, l - lb, rb - r});
lb = l;
rb = r;
cnt -= 2;
}
return ans;
}
