#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
pll ask(ll l, ll r) {
ll mn, mx;
MinMax(l, r, &mn, &mx);
return {mn, mx};
}
long long findGap(int T, int N) {
vector<ll> a(N+1);
if (T == 1) {
auto [l, r] = ask(1, 1e18);
int cur = 2;
a[1] = l, a[N] = r;
while (cur <= (N+1) / 2) {
auto [x, y] = ask(l+1, r-1);
a[cur] = x, a[N-cur+1] = y;
l = x, r = y;
cur++;
}
} else {
set<ll> b;
auto [l, r] = ask(1, 1e18);
a[1] = l, a[N] = r;
b.emplace(l), b.emplace(r);
for (int i = 2; i < N; i++) {
r = *b.lower_bound(l+1);
if (r == l+1) { a[i] = l+1, l++; continue; }
auto [x, y] = ask(l+1, r-1);
if (x == -1) a[i] = r;
else a[i] = x, b.emplace(y);
l = a[i];
}
}
ll mx = 0;
for (int i = 1; i <= N-1; i++) mx = max(mx, a[i+1] - a[i]);
return mx;
}
