#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)(1e18);
void MinMax(ll s, ll t, ll *mn, ll *mx);
ll findGap(int T, int N) {
if (T == 1) {
ll a, b;
MinMax(0, INF, &a, &b);
ll ans = 0;
while (a + 1 < b) {
N -= 2;
if (N == 0) break;
ll c, d;
MinMax(a + 1, b - 1, &c, &d);
ans = max(ans, c - a);
ans = max(ans, b - d);
a = c;
b = d;
}
ans = max(ans, b - a);
return ans;
}
ll first, last;
MinMax(0, INF, &first, &last);
ll pos = first, ans = 1, base = (last - first + N - 2) / (N - 1);
while (pos != last) {
ll cur = base;
while (true) {
ll a, b;
MinMax(pos + 1, pos + cur, &a, &b);
if (a == -1) {
base = cur;
cur *= 2;
continue;
}
ans = max(ans, a - pos);
pos = b;
break;
}
}
ans = max(ans, last - pos);
return ans;
}
