#include "gap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using namespace std;
using lli=long long;
using pll=pair<lli,lli>;
const lli INF=1000000000000000000ll;
lli sub1(int n) {
lli mx=0, lv=-1, rv=INF+1;
for(int i=0;i<(n+1)/2;i++) {
lli s=lv, t=rv, l, r;
MinMax(s+1, t-1, &l, &r);
if(i!=0) {
mx = max(mx, l-lv);
mx = max(mx, rv-r);
}
lv = l; rv = r;
}
if(!(n&1)) mx = max(mx, rv-lv);
return mx;
}
lli sub2(int n) {
lli s=0,f=INF,l,r;
MinMax(s, f, &l, &r);
lli seg = (r-l)/n,mx=0;
s=l+1;
while(s<r) {
f = s+seg;
if(f >= r) f=r-1;
lli lv,rv;
MinMax(s, f, &lv, &rv);
if(lv!=-1) {
mx = max(mx, lv-l);
l = rv;
}
}
mx = max(mx, r-l);
return mx;
}
long long findGap(int T, int N)
{
if(T==1) return sub1(N);
else return sub2(N);
return 0;
}
