#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7;
const int T = 1000 * 1000 * 1000;
const int INF = T * T;
int al[N], ar[N];
long long findGap(signed group, signed n)
{
if (group == 2) {
int l, r;
MinMax(0, INF, &l, &r);
if (n == 2)
return r - l;
int len = r - l + 1;
int k = len % (n - 1);
int t = len / (n - 1) + 1;
int ptr = l;
for (int i = 0; i < k; ++i) {
MinMax(ptr, ptr + t - 1, &al[i], &ar[i]);
ptr += t;
}
--t;
for (int i = k; i < n - 1; ++i) {
MinMax(ptr, ptr + t - 1, &al[i], &ar[i]);
ptr += t;
}
int ans = 0;
r = -1;
for (int i = 0; i < n - 1; ++i) {
if (al[i] == -1)
continue;
if (r != -1)
ans = max(ans, al[i] - r);
r = ar[i];
}
return ans;
}
else {
int l = -1, r = INF + 1;
int ans = 0;
for (int i = 0; i < (n + 1) / 2; ++i) {
int nl, nr;
MinMax(l + 1, r - 1, &nl, &nr);
if (nl == -1) {
break;
}
else {
if (l != -1)
ans = max(ans, nl - l);
if (r != INF + 1)
ans = max(ans, r - nr);
l = nl;
r = nr;
}
}
ans = max(ans, r - l);
return ans;
}
}
