// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int> >;
using pii = pair<int, int>;
void MinMax(long long s, long long t, long long *mn, long long *mx);
const int INF = 1e18;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
class solver {
public:
int Rand(int l, int r) {
return l + rnd() % (r - l + 1);
}
map<pii, pii> mem;
pii query(int a, int b) {
if (mem.contains({a,b}))
return mem[{a,b}];
if (a > b)
return mem[{a,b}]={-1, -1};
int u, v;
MinMax(a, b, &u, &v);
return mem[{a,b}]={u, v};
}
int answer;
int f(int l, int r) {
if (l > r)
return 0;
auto [u,v]=query(l,r);
if ( u == v || u == -1)
return 0;
l = u;
r = v;
int mid = Rand(l, r);
int res = 0;
res = max(res, f(l, mid));
res = max(res, f(mid+1, r));
int left = query(l, mid).S;
int right = query(mid+1, r).F;
if (left != -1 && right != -1) {
res = max(res, right - left);
}
return res;
}
solver(int t, int n) {
answer = f(0, INF);
}
};
int findGap(int32_t t, int32_t n) {
if (t == 1) {
}
if (t == 2) {
solver sol(t, n);
return sol.answer;
}
}
#undef int
