#ifndef EVAL
#include "grader.cpp"
#endif
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll findGap(int T, int n){
if(T == 1){
ll ans = 0;
ll l=0, r=1e18;
vector<ll> a(n+1);
ll mn, mx;
int idl = 1, idr = n;
while(idl <= idr){
MinMax(l, r, &mn, &mx);
a[idl] = mn;
a[idr] = mx;
l = mn+1, r = mx-1;
idl++;
idr--;
}
for(int i=2;i<=n;i++)ans = max(ans, a[i]-a[i-1]);
return ans;
}else {
ll l=0, r=1e18;
MinMax(l,r,&l,&r);
//~ if(r-l+1 == n){
//~ return 1;
//~ }
vector<pair<ll,ll>> v;
ll len = (r-l-n)/n;
ll nl=l, nr=l+len;
for(ll i=0;i<n;i++){
v.push_back({nl, nr});
nl += len+1, nr += len+1;
}v[v.size()-1].second = r;
//~ for(auto [x,y] : v){cout << x << ' ' << y << '\n';}cout << '\n';
ll ans = len;
ll last = 1e18;
for(auto [x,y] : v){
ll mn=0, mx=1e18;
MinMax(x,y,&mn,&mx);
ans = max(ans, mn - last);
last = mx;
}
return ans;
}
}
