#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;
}
ll len = (r-l+1)/n;
if((r-l+1)%n)len++;
ll ans = len;
ll last = l;
for(ll i=l;i<=r;i+=len){
ll askl = i;
if(askl == l)askl++;
ll mn,mx;
//~ cerr << "what the\n";
MinMax(askl,min(i+len-1,r),&mn,&mx);
//~ cerr << "OK\n";
if(mn == -1)continue;
ans = max(ans,mx-mn);
ans = max(ans,mn - last);
last = mx;
//~ cout << ans << '\n';
}
return ans;
}
}
