#include<iostream>
#include "gap.h"
#define l 1000000000000000000
using namespace std;
long long subt1(long long n)
{
long long tf,ts,pf,ps,mr=0;
MinMax(0,l,&tf,&ts);
for(int i=2;i<=n/2;i++)
{
pf=tf;ps=ts;
MinMax(pf+1,ps-1,&tf,&ts);
if(tf-pf>mr) mr=tf-pf;
if(ps-ts>mr) mr=ps-ts;
}
if(n%2)
{
if(tf+1<=ts-1)
MinMax(tf+1,ts-1,&pf,&ps);
if(pf-tf>mr) mr=pf-tf;
if(ts-pf>mr) mr=ts-pf;
}
else if(ts-tf>mr) mr=ts-tf;
return mr;
}
long long subt2(long long n)
{
long long tl,tr,le,ri,mi,ma,pma,mr=0;
MinMax(0,l,&tl,&tr);
long long in=(tr-tl+1)/(n-1);
le=tl+1;ri=tl+in;
pma=tl;
for(int i=1;i<n;i++)
{
MinMax(le,ri,&mi,&ma);
le+=in;ri+=in;
if(mi!=-1 && mr<mi-pma)
mr=mi-pma;
if(ma!=-1) pma=ma;
}
if(le<=tr)
{
MinMax(le,tr,&mi,&ma);
if(mi==-1)
{
mr=max(mr,tr+1-pma);
}
else
{
mr=max(mr,mi-pma);
mr=max(mr,tr+1-ma);
}
}
return mr;
}
long long findGap(int T, int N)
{
if(T==1)
return subt1(N);
else return subt2(N);
}
