#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dnc(int l, int r){
if (l>=r) return 0;
int mid=(l+r)>>1;
int l1, r1, l2, r2;
MinMax(l, mid, &l1, &r1);
MinMax(mid+1, r, &l2, &r2);
int ll=l1;
if (ll==-1) ll=l2;
int rr=r2;
if (rr==-1) rr=r1;
if (ll==-1 || rr==-1) return r-l+2;
return max({(r+1)-rr, ll-(l-1), l2-r1, dnc(l1+1, r1-1), dnc(l2+1, r2-1)});
}
long long findGap(int32_t T, int32_t N)
{
int l, r;
MinMax(0, 1e18, &l, &r);
if (N==2) return r-l;
return dnc(l+1, r-1);
}
