#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long lli;
typedef long long ll;
typedef vector<int32_t> vi;
typedef vector<ld> vld;
typedef vector<lli> vlli;
typedef pair<lli, lli> pii;
// #define int int64_t
#define endl "\n"
#define inp(n) lli n; cin >> n
#define inpstr(s) string s; cin >> s
#define inp2(a,b) lli a,b; cin >> a >> b
#define inparr(arr,n) lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define f0(i,n) for(int32_t i = 0; i < (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)
#define testIn cin >> test
#define tests for(int32_t testNo=1; testNo <= (test); testNo++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(a) ((int64_t)(a).size())
#define lcm(a, b) (((a)*(b))/gcd(a,b))
#define ff first
#define ss second
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define finish return 0
#define clean fflush(stdout)
#define Inf (lli)(1e9)
#define Eps (ld)(1e-9)
#define PI (ld)(3.141592653589793238462643383279502884197169L)
#define MOD (int32_t)(1e9+7)
template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
set<ll> nums;
long long findGap(int T, int N) {
ll mn, mx;
if(N == 2) {
MinMax(0, 1e18, &mn, &mx);
return mx - mn;
}
if(T == 1) {
MinMax(0, 1e18, &mn, &mx);
nums.insert(mn), nums.insert(mx);
while(true) {
MinMax(mn+1, mx-1, &mn, &mx);
if(mn == -1) break;
nums.insert(mn), nums.insert(mx);
if(mn + 1 >= mx) break;
if(nums.size() == N) break;
}
}
if(T == 2) {
MinMax(0, 1e18, &mn, &mx);
nums.insert(mn);
nums.insert(mx);
ll l = mn + 1, r = mx - 1;
N -= 2;
ll B = r - l + N;
B /= N;
if(B == 1) B++;
while(l <= r) {
MinMax(l, min(l+B-1, r), &mn, &mx);
if(mn != -1) {
nums.insert(mn);
nums.insert(mx);
}
l += B;
if(nums.size() == N+2) break;
}
}
ll ans = 0;
N = nums.size() - 1;
auto it = nums.begin();
f0(i, N) {
ans = max(ans, *next(it) - *it);
it = next(it);
}
return ans;
return 0;
}
