#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll Answer(vector<ll>a) {
int N = a.size();
ll answer = 0;
for (int i = 0 ; i < N - 1 ; ++ i) answer = max(answer, a[i + 1] - a[i]);
return answer;
}
ll solve1(int N) {
ll L = -1, R = ll(1e18)+1;
vector<ll>a(N);
int l = 0, r = N - 1;
while (l <= r) {
MinMax(L+1, R-1, &L, &R);
a[l++] = L, a[r--] = R;
}
return Answer(a);
}
vector<ll>a;
mt19937 rnd(random_device{}());
void solve(ll L, ll R) {
if (L > R) return;
ll M = (L + R) / 2;
ll X;
if (rnd() & 1 || 1) {
MinMax(L, M, &L, &X);
if (L != -1) a.emplace_back(L);
if (X != -1 && L != X) a.emplace_back(X);
if (L != -1 && X != -1) solve(L + 1, X - 1);
solve(M + 1, R);
} else {
MinMax(L, M, &X, &R);
if (R != -1) a.emplace_back(R);
if (X != -1 && R != X) a.emplace_back(X);
if (R != -1 && X != -1) solve(X + 1, R - 1);
solve(L, M - 1);
}
}
ll solve2(int N) {
ll L, R;
MinMax(0, ll(1e18), &L, &R);
a.emplace_back(L);
a.emplace_back(R);
solve(L + 1, R - 1);
sort(a.begin(), a.end());
assert((int)a.size() == N);
return Answer(a);
}
ll findGap(int T, int N) {
if (T == 1) {
return solve1(N);
} else {
return solve2(N);
}
}
