#include <bits/stdc++.h>
#include "gap.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;
ll mn, mx;
void query(ll L, ll R)
{
MinMax(L, R, &mn, &mx);
}
ll solve1(int n)
{
ll a[n];
mn=-1, mx=(ll)(1e18)+1;
for(int l=0, r=n-1; l<=r; l++, r--)
{
query(mn + 1, mx - 1);
a[l]=mn, a[r]=mx;
}
ll ans=0;
forn(i,1,n) ans=max(ans, a[i]-a[i-1]);
return ans;
}
ll solve2(int n)
{
query(0, (ll)1e18);
ll L=mn, R=mx;
ll len=(R-L+n-2) / (n-1);
vector<ll> v={mn};
forn(i,0,n-1)
{
query(L+i*len+1, L+(i+1)*len);
if(mn!=-1)
{
v.pb(mn); v.pb(mx);
}
}
ll ans=0;
forn(i,1,sz(v)) ans=max(ans, v[i]-v[i-1]);
return ans;
}
long long findGap(int T, int N)
{
return (T == 1 ? solve1(N) : solve2(N));
}
