#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
const ll MINN = 0;
const ll MAXN = 1e18;
ll solve1(int N) {
ll mn = MINN, mx = MAXN;
queue<ll> left;
stack<ll> right;
while(true) {
ll l, r;
MinMax(mn, mx, &l, &r);
if(l == r) {
left.push(l);
} else {
left.push(l);
right.push(r);
}
mn = l + 1;
mx = r - 1;
if(left.size() + right.size() == N) break;
}
vector<ll> a;
while(!left.empty()) {
a.push_back(left.front());
left.pop();
}
while(!right.empty()) {
a.push_back(right.top());
right.pop();
}
ll ans = 0;
for(int i = 1; i < N; i++) {
ans = max(ans, a[i] - a[i-1]);
}
return ans;
}
ll solve2(int N) {
ll rangeL, rangeR;
MinMax(0, MAXN, &rangeL, &rangeR);
ll step = ( (rangeR - rangeL - 1) + N - 1) / (N - 1);
ll ans = step, x, y, l = rangeL, i;
for(i = rangeL; i < rangeR; i += step + 1) {
MinMax(i, min(i + step, rangeR), &x, &y);
if(x != -1) {
ans = max(ans, x - l);
l = y;
}
}
return ans;
}
ll findGap(int T, int N) {
if(T == 1) {
return solve1(N);
} else if(T == 2) {
return solve2(N);
}
return 42;
}
