#include "gap.h"
#include <cstdio>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll OO = 1e18;
int cnt = 0;
pll query(ll a, ll b) {
if(a > b) { return {-1, -1}; }
ll ret, ret_;
++cnt;
MinMax(a, b, &ret, &ret_);
return {ret, ret_};
}
ll solve(ll lst, ll l, ll r, int n) {
if(n == 1) { return 0; }
pll res = query(l, l + (r - l) / (n - 1));
ll ret = res.X - lst;
pll res2 = query(res.X + 1, res.Y - 1);
// printf("%lld %lld %lld %d : %lld %lld %lld %lld\n", lst, l, r, n, res.X, res.Y, res2.X, res2.Y);
if(res2.X == -1) {
ret = max(ret, res.Y - res.X);
}
return ret = max(ret, solve(max(lst, res.Y), l + (r - l) / (n - 1) + 1, r, n - 1));
}
ll findGap(int T, int n) {
cnt = 0;
pll res = query(0, OO);
ll ret = solve(res.X, res.X, res.Y, n);
// if(cnt > 3 * n) { return -1; }
return ret;
}
