#include "gap.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<Int,Int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
pii query(Int l,Int r){
Int a, b;
MinMax(l,r, &a,&b);
return {a,b};
}
Int cdiv(Int a,Int b){
return (a-1)/b+1;
}
int n;
Int findGap(int T,int _n){
n = _n;
if(T==1){
V<Int> l, r;
{
auto[a,b] = query(0,1e18);
l = {a};
r = {b};
}
while((int)l.size() + (int)r.size() < n){
auto[a,b] = query(l.back()+1, r.back()-1);
l.push_back(a);
r.push_back(b);
}
reverse(all(r));
for(Int x : r) l.push_back(x);
Int prv = l[0], ans = 0;
for(Int x : l){
ans = max(ans, x-prv);
prv = x;
}
return ans;
}
auto[a1,an] = query(0,1e18);
Int len = cdiv(an-a1, n-1);
V<Int> a = {a1};
for(Int l=a1+1,r=l+len; l<an; l+=len,r+=len){
auto[x,y] = query(l,r);
if(x!=-1){
a.push_back(x);
a.push_back(y);
}
}
a.push_back(an);
Int ans = 0;
Int prv = a[0];
for(Int x : a){
ans = max(ans, x-prv);
prv = x;
}
return ans;
}
