#include <bits/stdc++.h>
// #include "grader.cpp"
#include "gap.h"
using namespace std;
long long findGap(int T, int N){
set<long long> s;
long long L, R;
if(T == 1){
MinMax(1, 1e18, &L, &R);
s.insert(L); s.insert(R);
for(int i = 1; i < (N + 1) >> 1; i++){
long long qs, qt;
MinMax(L + 1, R - 1, &qs, &qt);
s.insert(qs); s.insert(qt);
L = qs; R = qt;
}
}
else{
MinMax(1, 1e18, &L, &R);
long long X = (R - L) / ((N * 1ll) - 1);
X += (R - L) % ((N * 1ll) - 1) != 0;
long long qs, qt;
for(long long i = L + 1; i < R; i += X + 1){
MinMax(i, min(i + X, R - 1), &qs, &qt);
s.insert(qs); s.insert(qt);
}
s.erase(-1ll);
}
long long ans = 0, old = L;
for(auto x : s){
ans = max(ans, x - old);
old = x;
}
return ans;
}
