#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
long long ar[100005];
set<long long>s;
long long sub1(long long N){
for(int i=1;i<=N;i++)ar[i]=0;
long long l=0,r=1e18;
long long ll=1,rr=N;
while(ll<=rr){
MinMax(l,r,&l,&r);
ar[ll]=l,ar[rr]=r;
l++,r--;
ll++,rr--;
}
long long ans=0;
for(int i=1;i<N;i++)ans=max(ans,ar[i+1]-ar[i]);
return ans;
}
void solve(long long l,long long r){
if(l>r)return;
if(l==r){
MinMax(l,r,&l,&r);
if(l==-1)return;
else return void(s.insert(l));
}
long long m1=(l+r)/2;
long long m2=(l+r)/2+1;
MinMax(l,m1,&l,&m1);
if(m2<=r)MinMax(m2,r,&m2,&r);
if(l!=-1)s.insert(l);
if(m1!=l)s.insert(m1);
if(r!=-1)s.insert(m2);
if(m2!=r)s.insert(r);
if(l!=-1)solve(l+1,m1-1);
if(r!=-1)solve(m2+1,r-1);
}
long long sub2(int N){
if(N<=3)return sub1(N);
solve(0,1e18);
auto x=s.begin();
auto y=next(s.begin());
long long ans=0;
while(y!=s.end()){
ans=max(ans,(*y)-(*x));
x=next(x);
y=next(y);
}
return ans;
}
long long findGap(int T, int N)
{
if(T==1)return sub1(N);
return sub2(N);
}
